| Presentation | 2009-10-16 An Improved Approximation Lower Bound for Maximum Cardinality Almost Stable Matching Problem Koki HAMADA, Shuichi MIYAZAKI, Kazuo IWAMA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Biro et al. defined the problem of finding a maximum cardinality matching that contains minimum number of blocking pairs. They proved that (i) this problem is NP-hard and cannot be approximated within the ratio of n^<1-ε> for any constant ε>0 unless P=NP, where n is the number of men in an input, (ii) even if each preference list is of length at most 3, the problem remains NP-hard and there exists a constant δ(>1) such that this problem cannot be approximated within the ratio of δ unless P=NP, and (iii) if the length of preference lists of one sex is at most 2, this problem is solvable in polynomial time. In this paper, we improve the constant δ of (ii) to n^<1-ε> for any ε>0. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | the stable marriage problem / approximation algorithms / approximation ratio / polynomial-time reduction |
| Paper # | COMP2009-37 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2009/10/9(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 Improved Approximation Lower Bound for Maximum Cardinality Almost Stable Matching Problem |
| Sub Title (in English) | |
| Keyword(1) | the stable marriage problem |
| Keyword(2) | approximation algorithms |
| Keyword(3) | approximation ratio |
| Keyword(4) | polynomial-time reduction |
| 1st Author's Name | Koki HAMADA |
| 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 | 2009-10-16 |
| Paper # | COMP2009-37 |
| Volume (vol) | vol.109 |
| Number (no) | 235 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |