File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Appears in Collections:
Conference Paper: The Maximum-Weight Stable Matching Problem: Duality and Efficiency
| Title | The Maximum-Weight Stable Matching Problem: Duality and Efficiency |
|---|---|
| Authors | |
| Issue Date | 2011 |
| Publisher | Georgia State University |
| Citation | Atlanta Lecture Series in Combinatorics and Graph Theory II, Atlanta, GA, USA, 26-27 February 2011 How to Cite? |
| Abstract | Given a preference system (G,≺) and an integral weight function de ned on the edge set of G (not
necessarily bipartite), the maximum-weight stable matching problem is to nd a stable matching of (G, ≺ )
with maximum total weight. We study this NP-hard problem using linear programming and polyhedral
approaches, and show that the Rothblum system for de ning the fractional stable matching polytope of
(G, ≺ ) is totally dual integral if and only if this polytope is integral if and only if (G, ≺ ) contains no so-
called semistable partitions with odd cycles. We also present a combinatorial polynomial-time algorithm
for the maximum-weight stable matching problem and its dual on any preference system containing no semistable partitions with odd cycles. (Joint work with X. Chen, G. Ding, and X. Hu.) |
| Persistent Identifier | http://hdl.handle.net/10722/241484 |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Zang, W | - |
| dc.date.accessioned | 2017-06-16T10:02:46Z | - |
| dc.date.available | 2017-06-16T10:02:46Z | - |
| dc.date.issued | 2011 | - |
| dc.identifier.citation | Atlanta Lecture Series in Combinatorics and Graph Theory II, Atlanta, GA, USA, 26-27 February 2011 | - |
| dc.identifier.uri | http://hdl.handle.net/10722/241484 | - |
| dc.description.abstract | Given a preference system (G,≺) and an integral weight function de ned on the edge set of G (not necessarily bipartite), the maximum-weight stable matching problem is to nd a stable matching of (G, ≺ ) with maximum total weight. We study this NP-hard problem using linear programming and polyhedral approaches, and show that the Rothblum system for de ning the fractional stable matching polytope of (G, ≺ ) is totally dual integral if and only if this polytope is integral if and only if (G, ≺ ) contains no so- called semistable partitions with odd cycles. We also present a combinatorial polynomial-time algorithm for the maximum-weight stable matching problem and its dual on any preference system containing no semistable partitions with odd cycles. (Joint work with X. Chen, G. Ding, and X. Hu.) | - |
| dc.language | eng | - |
| dc.publisher | Georgia State University | - |
| dc.relation.ispartof | Atlanta Lecture Series in Combinatorics and Graph Theory | - |
| dc.title | The Maximum-Weight Stable Matching Problem: Duality and Efficiency | - |
| dc.type | Conference_Paper | - |
| dc.identifier.email | Zang, W: wzang@maths.hku.hk | - |
| dc.identifier.authority | Zang, W=rp00839 | - |
| dc.identifier.hkuros | 190499 | - |
| dc.publisher.place | Atlanta, USA | - |