Downloads: 166

Files in This Item:
File Description SizeFormat 
IEICE_tec.rep_COMP2009-37.pdf2.22 MBAdobe PDFView/Open
Title: 最大サイズ最大安定度マッチング問題に対する近似下限の改良
Other Titles: An Improved Approximation Lower Bound for Maximum Cardinality Almost Stable Matching Problem
Authors: 濱田, 浩気  KAKEN_name
宮崎, 修一  KAKEN_name
岩間, 一雄  KAKEN_name
Author's alias: Hamada, Koki
Miyazaki, Shuichi
Iwama, Kazuo
Keywords: 安定結婚問題
the stable marriage problem
approximation algorithms
approximation ratio
polynomial-time reduction
Issue Date: 9-Oct-2009
Publisher: 電子情報通信学会
Journal title: 電子情報通信学会技術研究報告
Volume: 109
Issue: 235
Start page: 35
End page: 40
Thesis number: COMP2009-37
Abstract: 安定結婚問題で不完全希望リストを許すと, 同じ例題に対する全ての安定マッチングは同サイズになる.しかし, 安定性を無視すると, 一般にはそれよりも大きなサイズのマッチングが存在する.Biroらは, 最大サイズのマッチングの中で出来るだけブロッキングペア数の少ないマッチングを求める問題を提案した.彼らは, (i)この問題がNP困難であり, 任意の正定数εに対してP≠NPの仮定の下でn^<1-ε>-近似アルゴリズムを持たないこと(nは例題中の男性の数), (ii)希望リストの長さを3以下に制限してもNP困難であり, ある定数δ>1が存在しP≠NPの仮定の下でδ-近似アルゴリズムを持たないこと, (iii)片側の性(例えば男性)の希望リストの長さが全て2以下ならば多項式時間で解けること, を示した.本論文では, 上記(ii)の近似不可能性を, 定数δからn^<1-ε>(εは任意の正定数)へと改良した.
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.
Description: <コンピュテーション研究会(COMP)> 2009年10月16日(金) 10:00 - 16:35, 東北大学 青葉山キャンパス 電子情報システム・応物系 南講義棟103講義室
Rights: ©2009 by IEICE
Related Link:
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks

Export Format: 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.