The ALT auction algorithm for bipartite matching works without freezing, admits an augmenting-path analysis, and requires Θ(1/ε²) iterations even on paths.
Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints.ACM Trans
1 Pith paper cite this work, alongside 20 external citations. Polarity classification is still indexing.
1
Pith paper citing it
20
external citations · OpenAlex
fields
cs.DS 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
On the Assadi Liu Tarjan Auction Algorithm for Bipartite Matching: Simplification, Alternative Analysis, and Hard Instance
The ALT auction algorithm for bipartite matching works without freezing, admits an augmenting-path analysis, and requires Θ(1/ε²) iterations even on paths.