Skip to main content

Python package containing approximations of various NP problems.

Project description

Travis CI build SonarCloud Quality SonarCloud Maintainability Codacy Maintainability Maintainability Pypi project Pypi total project downloads

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:

Coveralls Coverage SonarCloud Coverage Code Climate Coverate

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

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for approximations, version 1.0.0
Filename, size File type Python version Upload date Hashes
Filename, size approximations-1.0.0.tar.gz (5.3 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page