Paper Info
Title
The Maximum-Weight Stable Matching Problem: Duality and Efficiency.
Abstract
Given a preference system (G, <) and an integral weight function defined on the edge set of G (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of (G, <) with maximum total weight. In this paper we study this NP-hard problem using linear programming and polyhedral approaches. We show that the Rothblum system for defining the fractional stable matching polytope of (G, <) is totally dual integral if and only if this polytope is integral if and only if (G, <) has a bipartite representation. We also present a combinatorial polynomial-time algorithm for the maximum-weight stable matching problem and its dual on any preference system with a bipartite representation. Our results generalize Kiraly and Pap's theorem on the maximum-weight stable-marriage problem and rely heavily on their work.
Year
DOI
Venue
2012
10.1137/120864866
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
Field
DocType
stable matching,linear system,integral polytope,total dual integrality,polynomial-time algorithm
Discrete mathematics,Combinatorics,Stable marriage problem,Weight function,Bipartite graph,Total dual integrality,Polytope,Duality (optimization),Linear programming,3-dimensional matching,Mathematics
Journal
Volume
Issue
ISSN
26
3
0895-4801
Citations 
PageRank 
References 
2
0.43
10
Authors
4
Name
Order
Citations
PageRank
Xujin Chen123130.54
Guoli Ding244451.58
Xiaodong Hu362847.63
Wenan Zang430539.19