Python package containing approximations of various NP problems.

## Project description

Python package containing approximations of various NP problems.

## How do I install this package?

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 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]

## Project details

Uploaded source