| Presentation | 2002/12/12 An Aprroximation Algorithm for the Stable Marriage Problem with Ties of Length Two Hiroki YANAGISAWA, Shuichi MIYAZAKI, Kazuo IWAMA, Magnus HALLDORSSON, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | While the original stable marriage problem requires all participants to rank all members of the opposite sex in a strict order, two natural variations are to allow for incomplete preference lists and ties in the preferences. Either variation is polynomially solvable, but it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, approximation of factor two is trivial. In this paper, we give a first nontrivial result for approximation of factor less than two. Our algorithm achieves a factor of 25/13(< 1.924) for a restricted case where each tie is of length two. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | the stable marriage problem / NP-hardness / ties / incomplete lists / approximation algorithms |
| Paper # | COMP2002-59 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2002/12/12(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Aprroximation Algorithm for the Stable Marriage Problem with Ties of Length Two |
| Sub Title (in English) | |
| Keyword(1) | the stable marriage problem |
| Keyword(2) | NP-hardness |
| Keyword(3) | ties |
| Keyword(4) | incomplete lists |
| Keyword(5) | approximation algorithms |
| 1st Author's Name | Hiroki YANAGISAWA |
| 1st Author's Affiliation | Graduate School of Informatics, Kyoto University() |
| 2nd Author's Name | Shuichi MIYAZAKI |
| 2nd Author's Affiliation | Academic Center for Computing and Media Studies, Kyoto University |
| 3rd Author's Name | Kazuo IWAMA |
| 3rd Author's Affiliation | Graduate School of Informatics, Kyoto University |
| 4th Author's Name | Magnus HALLDORSSON |
| 4th Author's Affiliation | Science Institute, University of Iceland |
| Date | 2002/12/12 |
| Paper # | COMP2002-59 |
| Volume (vol) | vol.102 |
| Number (no) | 522 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |