The Maximum-Weight Stable Matching Problem: Duality and Efficiency

DOI10.1137/120864866MaRDI QIDQ4899065zbMATH OpenOpenAlexFDO

Authors Guoli Ding, Xiaodong Hu, Wenan Zang, Xujin Chen

Publication date 4 January 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10722/164177

zbMATH Keywords

integral polytopelinear systempolynomial-time algorithmstable matchingtotal dual integrality

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• An algorithm for the maximum weight strongly stable matching problem
• Stable Matchings, Optimal Assignments, and Linear Programming
• A generalization of the stable matching problem
• A unifying approach to the structures of the stable matching problems
• A further note on the stable matching problem
• Stability, optimality and manipulation in matching problems with weighted preferences
• Some remarks on the stable matching problem
• A New Approach to Stable Matching Problems
• An improved approximation lower bound for finding almost stable maximum matchings

Cited in

(6)

• Stability, optimality and manipulation in matching problems with weighted preferences
• Stable fractional matchings
• Marriage market with indifferences: a linear programming approach
• On the diameter of lattice polytopes
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• Maximum-utility popular matchings with bounded instability

This page was built for publication: The Maximum-Weight Stable Matching Problem: Duality and Efficiency

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