File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/120864866
- Scopus: eid_2-s2.0-84867310086
- WOS: WOS:000309976400032
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: The Maximum-Weight Stable Matching Problem: Duality and Efficiency
Title | The Maximum-Weight Stable Matching Problem: Duality and Efficiency |
---|---|
Authors | |
Keywords | Integral polytope Linear system Polynomial-time algorithm Stable matching Total dual integrality |
Issue Date | 2012 |
Publisher | Society 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? |
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 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 Identifier | http://hdl.handle.net/10722/164177 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 1.031 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chen, X | - |
dc.contributor.author | Ding, G | - |
dc.contributor.author | Hu, X | - |
dc.contributor.author | Zang, W | - |
dc.date.accessioned | 2012-09-20T07:56:18Z | - |
dc.date.available | 2012-09-20T07:56:18Z | - |
dc.date.issued | 2012 | - |
dc.identifier.citation | SIAM Journal on Discrete Mathematics, 2012, v. 26 n. 3, p. 1346-1360 | - |
dc.identifier.issn | 0895-4801 | - |
dc.identifier.uri | http://hdl.handle.net/10722/164177 | - |
dc.description.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 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.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php | - |
dc.relation.ispartof | SIAM Journal on Discrete Mathematics | - |
dc.rights | © 2012 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Discrete Mathematics in volume 26, issue 3, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Integral polytope | - |
dc.subject | Linear system | - |
dc.subject | Polynomial-time algorithm | - |
dc.subject | Stable matching | - |
dc.subject | Total dual integrality | - |
dc.title | The Maximum-Weight Stable Matching Problem: Duality and Efficiency | - |
dc.type | Article | - |
dc.identifier.email | Zang, W: wzang@maths.hku.hk | - |
dc.identifier.authority | Zang, W=rp00839 | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1137/120864866 | - |
dc.identifier.scopus | eid_2-s2.0-84867310086 | - |
dc.identifier.hkuros | 205948 | - |
dc.identifier.volume | 26 | - |
dc.identifier.issue | 3 | - |
dc.identifier.spage | 1346 | - |
dc.identifier.epage | 1360 | - |
dc.identifier.isi | WOS:000309976400032 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 0895-4801 | - |