Fast Interior Point Methods for Bipartite Matching

DOI10.1137/0805036MaRDI QIDQ4862781zbMATH OpenOpenAlexFDO

Authors Lov K. Grover

Publication date 1 February 1996

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0805036

zbMATH Keywords

approximate bipartite matchingapproximate matching algorithmnetwork flownonlogarithmic potential functionspath following interior point methods

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Deterministic network models in operations research (90B10) Linear programming (90C05) Combinatorial optimization (90C27)

Recommendations

• Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems
• Sublinear-Time Parallel Algorithms for Matching and Related Problems
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Faster scaling algorithms for general graph matching problems
• Perfect matchings in O(n n) time in regular bipartite graphs

Cited in

(2)

• Faster bottleneck non-crossing matchings of points in convex position
• Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems

This page was built for publication: Fast Interior Point Methods for Bipartite Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4862781)