| Presentation | 2004/4/15 Approximating the Stable Marriage Problem by Local Search Kazuya OKAMOTO, Shuichi MIYAZAKI, Kazuo IWAMA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both of these 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, an approximation algorithm with a factor two is trivial. There are several contributions that give approximation algorithms with factor better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio 2-c(log N)/N for an arbitrarily positive constant c, where N denotes the number of men in an input. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | the stable marriage problem / incomplete lists / ties / approximation algorithms / local search |
| Paper # | COMP2004-8 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2004/4/15(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) | Approximating the Stable Marriage Problem by Local Search |
| Sub Title (in English) | |
| Keyword(1) | the stable marriage problem |
| Keyword(2) | incomplete lists |
| Keyword(3) | ties |
| Keyword(4) | approximation algorithms |
| Keyword(5) | local search |
| 1st Author's Name | Kazuya OKAMOTO |
| 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 |
| Date | 2004/4/15 |
| Paper # | COMP2004-8 |
| Volume (vol) | vol.104 |
| Number (no) | 16 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |