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

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)

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

(5)

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

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)