Python package containing approximations of various NP problems.
Project description
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]
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
approximations-1.0.0.tar.gz
(5.3 kB
view hashes)