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

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

Jay Sethuraman, Chung-Piaw Teo

Publication date: 30 August 2000

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

zbMATH Keywords

linear programmingapproximation algorithmrandomized roundingstable matchingcutting-plane heuristic

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

How hard is it to satisfy (almost) all roommates ⋮ A polynomial-time algorithm for the bistable roommates problem ⋮ Pairwise kidney exchange

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

This page was built for publication: On a cutting plane heuristic for the stable roommates problem and its applications