The Maximum-Weight Stable Matching Problem: Duality and Efficiency

DOI10.1137/120864866zbMATH Open1282.90105OpenAlexW2085721624MaRDI QIDQ4899065FDOQ4899065

Xujin Chen, Wenan Zang, Xiaodong Hu, Guoli Ding

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

Recommendations

• scientific article; zbMATH DE number 7561396
• 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

zbMATH Keywords

linear systempolynomial-time algorithmstable matchingtotal dual integralityintegral polytope

Mathematics Subject Classification ID

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

Cited In (5)

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

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)