ダウンロード数: 278
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
transinf_E89-D_2380.pdf | 225.27 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Iwama, Kazuo | en |
dc.contributor.author | Miyazaki, Shuichi | en |
dc.contributor.author | Okamoto, Kazuya | en |
dc.contributor.alternative | 岩間, 一雄 | ja |
dc.contributor.alternative | 宮崎, 修一 | ja |
dc.contributor.alternative | 岡本, 和也 | ja |
dc.date.accessioned | 2017-09-08T01:38:57Z | - |
dc.date.available | 2017-09-08T01:38:57Z | - |
dc.date.issued | 2006-08-01 | - |
dc.identifier.issn | 0916-8532 | - |
dc.identifier.uri | http://hdl.handle.net/2433/227018 | - |
dc.description.abstract | 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 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. A few approximation algorithms have been proposed with approximation ratio 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 A [2-c log N/N] for an arbitrarily positive constant c, where N denotes the number of men in an input. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Institute of Electronics, Information and Communications Engineers (IEICE) | en |
dc.publisher.alternative | 電子情報通信学会 | ja |
dc.rights | © 2006 The Institute of Electronics, Information and Communication Engineers | en |
dc.subject | stable marriage problem | en |
dc.subject | incomplete lists | en |
dc.subject | ties | en |
dc.subject | approximation algorithms | en |
dc.subject | local search | en |
dc.title | A (2-c log N/N)-Approximation Algorithm for the Stable Marriage Problem | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.jtitle | IEICE TRANSACTIONS on Information and Systems | - |
dc.identifier.volume | E89-D | - |
dc.identifier.issue | 8 | - |
dc.identifier.spage | 2380 | - |
dc.identifier.epage | 2387 | - |
dc.textversion | publisher | - |
dc.address | Graduate School of Informatics, Kyoto University | en |
dc.address | Academic Center for Computing and Media Studies, Kyoto University | en |
dc.address | Graduate School of Informatics, Kyoto University | en |
dc.relation.url | http://search.ieice.org/bin/summary.php?id=e89-d_8_2380&category=D&year=2006&lang=E&abst= | - |
dcterms.accessRights | open access | - |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。