sparse_linear_assignment 0.1.5

Solvers for sparse linear assignment problem based on the auction algorithm
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//! # Sparse linear assignment
//! Solvers for weighted perfect matching problem ([linear assignment](https://en.wikipedia.org/wiki/Assignment_problem)) for bipartite graphs. Both solvers use variants of auction algorithm and implemented in Rust.
//!
//!    * [KhoslaSolver](KhoslaSolver) is best suited for asymmetric k-regular sparse graphs. The algorithm is presented in [this paper](https://arxiv.org/pdf/2101.07155.pdf). It stops in finite number of iterations.
//!    * [ForwardAuctionSolver](ForwardAuctionSolver) works better for symmetric assignment problems. It uses ε-scaling to speedup the auction algorithm. The implementation is based on [sslap](https://github.com/OllieBoyne/sslap). When there is no perfect matching it enters in endless loop and stops after `max_iterations` number of iterations.

#[cfg(feature = "khosla")]
pub use crate::ksparse::KhoslaSolver;
pub use crate::solution::AuctionSolution;
pub use crate::solver::AuctionSolver;
#[cfg(feature = "forward")]
pub use crate::symmetric::ForwardAuctionSolver;

#[cfg(feature = "khosla")]
pub mod ksparse;
pub mod solution;
pub mod solver;
#[cfg(feature = "forward")]
pub mod symmetric;