Maintaining perfect matchings at low cost

DOI10.4230/LIPICS.ICALP.2019.82MaRDI QIDQ5091241zbMATH OpenFDO

Authors Jannik Matuschke, Ulrike Schmidt-Kraepelin, José Verschae

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1811.10580

zbMATH Keywords

approximation algorithmsmatchingsrobust optimization

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• scientific article; zbMATH DE number 7238962
• Changing bases: multistage optimization for matroids and matchings
• A robust and optimal online algorithm for minimum metric bipartite matching
• Robust Matchings
• Robust matchings and matroid intersections

Cites work

• A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints
• A robust and optimal online algorithm for minimum metric bipartite matching
• Edmonds, matching and the birth of polyhedral combinatorics
• Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming
• Maximum matching and a polyhedron with 0,1-vertices
• On a Greedy Heuristic for Complete Matching
• On-line algorithms for weighted bipartite matching and stable marriages
• Online bipartite matching with amortized O(^2 n) replacements
• Online matching on a line
• Online perfect matching and mobile computing
• Online Steiner tree with deletions
• Online Weighted Matching
• Robust recoverable perfect matchings
• The concept of recoverable robustness, linear programming recovery, and railway applications
• The Online Metric Matching Problem for Doubling Metrics
• The power of deferral: maintaining a constant-competitive Steiner tree online
• The power of recourse for online MST and TSP
• Weighted Matching in Chess Tournaments
• Weighted matching with vertex weights: An application to scheduling training sessions in NASA space shuttle cockpit simulators

Cited in

(6)

• Low weight perfect matchings
• scientific article; zbMATH DE number 7758339 (Why is no real title available?)
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching
• Online deterministic minimum cost bipartite matching with delays on a line
• Online deterministic minimum cost bipartite matching with delays on a line
• Online metric matching on the line with recourse

This page was built for publication: Maintaining perfect matchings at low cost

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