Product
Introducing License Enforcement in Socket
Ensure open-source compliance with Socket’s License Enforcement Beta. Set up your License Policy and secure your software!
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 a Cython implementation of the Auction Algorithm [1], which is 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.
Also provided is an implementation of the Hopcroft-Karp Algorithm [2] for finding a maximum matching in a bipartite graph. This is used by the Auction solver to check that a given problem has a valid solution.
Tested on Windows (Python 3.8):
pip install sslap
Tested on Linux (Python 3.7):
pip install git+https://github.com/OllieBoyne/sslap.git
examples/test_auction.py
examples/test_feasibility.py
The algorithm is best suited for large and sparse problems, where it outperforms scipy.optimize.linear_sum_assignment
.
See below for some timed comparisons of the runtime for problems of varying density (% of valid entries in the matrix) and matrix size.
cardinality_check=False
to auction_solve[1] Bertsekas, D. A Distributed Algorithm for the Assignment Problem (1979)
[2] Hopcroft J. Karp, R. An n^(5/2) algorithm for maximum matchings in bipartite graphs (1973)
FAQs
Super Sparse Linear Assignment Problems Solver
We found that sslap demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Product
Ensure open-source compliance with Socket’s License Enforcement Beta. Set up your License Policy and secure your software!
Product
We're launching a new set of license analysis and compliance features for analyzing, managing, and complying with licenses across a range of supported languages and ecosystems.
Product
We're excited to introduce Socket Optimize, a powerful CLI command to secure open source dependencies with tested, optimized package overrides.