On a cutting plane heuristic for the stable roommates problem and its applications

DOI10.1016/S0377-2217(99)00049-1zbMath0961.90092MaRDI QIDQ1577118

Chung-Piaw Teo, Jay Sethuraman

Publication date: 30 August 2000

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

linear programming; approximation algorithm; randomized rounding; stable matching; cutting-plane heuristic

Mathematics Subject Classification ID

90C05: Linear programming

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

Pairwise kidney exchange, A polynomial-time algorithm for the bistable roommates problem

Cites Work

• Unnamed Item
• Linear programming brings marital bliss
• Characterization of stable matchings as extreme points of a polytope
• A bounded approximation for the minimum cost 2-sat problem
• A new fixed point approach for stable networks and stable marriages
• Stable matchings and linear inequalities
• Stable matchings and linear programming
• The Geometry of Fractional Stable Matchings and Its Applications
• An efficient algorithm for the “stable roommates” problem
• Stable Matchings, Optimal Assignments, and Linear Programming
• A New Approach to Stable Matching Problems
• Maximum matching and a polyhedron with 0,1-vertices
• College Admissions and the Stability of Marriage