講演抄録/キーワード |
講演名 |
2005-05-20 15:30
安定結婚問題に対する局所探索近似アルゴリズムの改良 ○山内直哉・宮崎修一・岩間一雄(京大) |
抄録 |
(和) |
安定結婚問題において,同順位リストと不完全リストの存在を許した問題に対して最大サイズの安定マッチングを見つける問題を考える.この問題はNP困難であり,現在知られている最良の近似アルゴリズムは,($2-c\frac{\log N}{N}$)-近似アルゴリズムである.(ここで,$c$は任意の正定数であり,$N$は入力中の男性の数である.)本論文では,この近似度を$2-c\frac{1}{N^\frac{2}{3}}$に改良した.($c$は$c \leq \frac{1}{2\sqrt[3]{6}}$を満たす正定数である.) |
(英) |
We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. This problem is NP-hard and the current best known approximation algorithm achieves the approximation ratio $2-c\frac{\log N}{N}$, where $c$ is an arbitrary positive constant and $N$ is the number of men in an input. In this paper, we improve the ratio to $2-c\frac{1}{N^\frac{2}{3}}$, where $c$ is a constant such that $c \leq \frac{1}{2 \sqrt[3]{6}}$. |
キーワード |
(和) |
安定結婚問題 / 不完全リスト / 同順位 / 近似アルゴリズム / 局所探索法 / / / |
(英) |
the stable marriage problem / incomplete lists / ties / approximation algorithms / local search / / / |
文献情報 |
信学技報, vol. 105, no. 72, COMP2005-15, pp. 45-51, 2005年5月. |
資料番号 |
COMP2005-15 |
発行日 |
2005-05-13 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|
研究会情報 |
研究会 |
COMP |
開催期間 |
2005-05-20 - 2005-05-20 |
開催地(和) |
九州大学 |
開催地(英) |
Kyushu Univ. |
テーマ(和) |
|
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
COMP |
会議コード |
2005-05-COMP |
本文の言語 |
日本語 |
タイトル(和) |
安定結婚問題に対する局所探索近似アルゴリズムの改良 |
サブタイトル(和) |
|
タイトル(英) |
Improving a local search approximation algorithm for the stable marriage problem |
サブタイトル(英) |
|
キーワード(1)(和/英) |
安定結婚問題 / the stable marriage problem |
キーワード(2)(和/英) |
不完全リスト / incomplete lists |
キーワード(3)(和/英) |
同順位 / ties |
キーワード(4)(和/英) |
近似アルゴリズム / approximation algorithms |
キーワード(5)(和/英) |
局所探索法 / local search |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
山内 直哉 / Naoya Yamauchi / ヤマウチ ナオヤ |
第1著者 所属(和/英) |
京都大学 (略称: 京大)
Kyoto University (略称: Kyoto Univ.) |
第2著者 氏名(和/英/ヨミ) |
宮崎 修一 / Shuichi Miyazaki / ミヤザキ シュウイチ |
第2著者 所属(和/英) |
京都大学 (略称: 京大)
Kyoto University (略称: Kyoto Univ.) |
第3著者 氏名(和/英/ヨミ) |
岩間 一雄 / Kazuo Iwama / イワマ カズオ |
第3著者 所属(和/英) |
京都大学 (略称: 京大)
Kyoto University (略称: Kyoto Univ.) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2005-05-20 15:30:00 |
発表時間 |
35分 |
申込先研究会 |
COMP |
資料番号 |
COMP2005-15 |
巻番号(vol) |
vol.105 |
号番号(no) |
no.72 |
ページ範囲 |
pp.45-51 |
ページ数 |
7 |
発行日 |
2005-05-13 (COMP) |