File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: The Maximum-Weight Stable Matching Problem: Duality and Efficiency

TitleThe Maximum-Weight Stable Matching Problem: Duality and Efficiency
Authors
Issue Date2012
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php
Citation
SIAM Journal on Discrete Mathematics, 2012, v. 26 n. 3, p. 1346-1360 How to Cite?
AbstractGiven 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 Király and Pap's theorem on the maximum-weight stable-marriage problem and rely heavily on their work. © 2012 Society for Industrial and Applied Mathematics.
Persistent Identifierhttp://hdl.handle.net/10722/164177
ISSN
2015 SCImago Journal Rankings: 1.230

 

DC FieldValueLanguage
dc.contributor.authorChen, X-
dc.contributor.authorDing, G-
dc.contributor.authorHu, X-
dc.contributor.authorZang, W-
dc.date.accessioned2012-09-20T07:56:18Z-
dc.date.available2012-09-20T07:56:18Z-
dc.date.issued2012-
dc.identifier.citationSIAM Journal on Discrete Mathematics, 2012, v. 26 n. 3, p. 1346-1360-
dc.identifier.issn1095-7146-
dc.identifier.urihttp://hdl.handle.net/10722/164177-
dc.description.abstractGiven 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 Király and Pap's theorem on the maximum-weight stable-marriage problem and rely heavily on their work. © 2012 Society for Industrial and Applied Mathematics.-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php-
dc.relation.ispartofSIAM Journal on Discrete Mathematics-
dc.rightsSIAM Journal on Discrete Mathematics. Copyright © Society for Industrial and Applied Mathematics.-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.titleThe Maximum-Weight Stable Matching Problem: Duality and Efficiency-
dc.typeArticle-
dc.identifier.emailZang, W: wzang@maths.hku.hk-
dc.identifier.authorityZang, W=rp00839-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/120864866-
dc.identifier.hkuros205948-
dc.identifier.volume26-
dc.identifier.issue3-
dc.identifier.spage1346-
dc.identifier.epage1360-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats