Super Sparse Linear Assignment Problems Solver
Project description
SSLAP
This library provides implementations for solvers for Super Sparse Linear Assignment Problems.
An assignment problem is one where a one-to-one assignment has to be made between two sets, where each assignment has an associated cost.
In super sparse assignment problems, typically less than 1% of all feasible assignments are allowed.
This library provides two algorithms:
- Auction Algorithm - An algorithm well suited for super sparse problems. It is one in which people in one set 'bid' for objects in the other set, driving up their prices in order to find an optimal assignment.
- Sparse Hungarian - A simple implementation of the Hungarian Algorithm, leveraged for sparse matrices
Both of these problems are implemented in Cython, with a pure Python implementation of the Hungarian algorithm also provided.
Installation
pip install -e .
Benchmarking
Notes
- A matrix passed into from_matrix requires positive values only, and -1 indicates invalid values.
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
sslap-0.1.tar.gz
(255.6 kB
view hashes)
Built Distribution
sslap-0.1-cp38-cp38-win_amd64.whl
(160.5 kB
view hashes)
Close
Hashes for sslap-0.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ef159041aab699f16d3caabb5a651711b7d1cda61ed0f59506c3f7389210c283 |
|
MD5 | e20286d14a06ab725a147cefc25f80ad |
|
BLAKE2b-256 | 71db18a0f587aba162800d6a3a3313ab3a77bfcec1d8fd47872297e056a2f210 |