Crate sparse_linear_assignment

Sparse linear assignment

Solvers for weighted perfect matching problem (linear assignment) for bipartite graphs. Both solvers use variants of auction algorithm and implemented in Rust.

• KhoslaSolver is best suited for asymmetric k-regular sparse graphs. The algorithm is presented in this paper. It stops in finite number of iterations.
• ForwardAuctionSolver works better for symmetric assignment problems. It uses ε-scaling to speedup the auction algorithm. The implementation is based on sslap. When there is no perfect matching it enters in endless loop and stops after max_iterations number of iterations.

Re-exports

pub use crate::ksparse::KhoslaSolver;
pub use crate::solution::AuctionSolution;
pub use crate::solver::AuctionSolver;
pub use crate::symmetric::ForwardAuctionSolver;

Modules

ksparse
solution
solver
symmetric