approximations 1.0.0

Python package containing approximations of various NP problems.

Python package containing approximations of various NP problems.

How do I install this package?

As usual, just download it using pip:

pip install approximations

Tests Coverage

Since some software handling coverages sometime get slightly different results, here’s three of them:

Available approximations

Knapsack

Knapsack is approximated using a FPTAS, with arbitrarily good approximation. The computing cost increases up to becoming NP as the approximation approaches 0.

from approximations import knapsack

total_weight, total_value, selected_objects = knapsack(
    weights=[1,2,3,4, 1, 2, 2, 2, 2, 2],
    values=[3,2,1,2,  1, 2, 2, 2, 2, 56],
    capacity=20,
    approximation=0.1
) # (18, 72, [0, 1, 3, 4, 5, 6, 7, 8, 9])

Load Balancing

Load Balancing is approximated using a 1.5-approximation greedy algorithm.

from approximations import load_balancing

assignment, makespans = load_balancing([1,2,3,4,5,6], 3) # ([[5, 0], [4, 1], [3, 2]], [7, 7, 7])

Set Cover

Load Balancing is approximated using a greedy algorithm.

from approximations image set_cover

cover = set_cover(
    {1, 2, 3, 4, 5},
    [{1, 2}, {3}, {1, 2, 3, 4}, {1, 3, 5}],
    [1, 2, 3, 4]
) # [0, 2, 3]