### Skapa referens, olika format (klipp och klistra)

**Harvard**

Huang, C., Iwama, K., Miyazaki, S. och Yanagisawa, H. (2015) *A tight approximation bound for the stable marriage problem with restricted ties*.

** BibTeX **

@conference{

Huang2015,

author={Huang, Chien-Chung and Iwama, K. and Miyazaki, S. and Yanagisawa, H.},

title={A tight approximation bound for the stable marriage problem with restricted ties},

booktitle={Leibniz International Proceedings in Informatics, LIPIcs},

isbn={978-393989789-7},

pages={361-380},

abstract={© Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa. The problem of finding a maximum cardinality stable matching in the presence of ties and unacceptable partners, called MAX SMTI, is a well-studied NP-hard problem. The MAX SMTI is NP-hard even for highly restricted instances where (i) ties appear only in women's preference lists and (ii) each tie appears at the end of each woman's preference list. The current best lower bounds on the approximation ratio for this variant are 1.1052 unless P=NP and 1.25 under the unique games conjecture, while the current best upper bound is 1.4616. In this paper, we improve the upper bound to 1.25, which matches the lower bound under the unique games conjecture. Note that this is the first special case of the MAX SMTI where the tight approximation bound is obtained. The improved ratio is achieved via a new analysis technique, which avoids the complicated case-by-case analysis used in earlier studies. As a by-product of our analysis, we show that the integrality gap of natural IP and LP formulations for this variant is 1.25. We also show that the unrestricted MAX SMTI cannot be approximated with less than 1.5 unless the approximation ratio of a certain special case of the minimum maximal matching problem can be improved.},

year={2015},

keywords={Approximation algorithm, Integer program, Integrality gap, Linear program relaxation, Stable marriage with ties and incomplete lists},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 232660

A1 Huang, Chien-Chung

A1 Iwama, K.

A1 Miyazaki, S.

A1 Yanagisawa, H.

T1 A tight approximation bound for the stable marriage problem with restricted ties

YR 2015

T2 Leibniz International Proceedings in Informatics, LIPIcs

SN 978-393989789-7

SP 361

OP 380

AB © Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa. The problem of finding a maximum cardinality stable matching in the presence of ties and unacceptable partners, called MAX SMTI, is a well-studied NP-hard problem. The MAX SMTI is NP-hard even for highly restricted instances where (i) ties appear only in women's preference lists and (ii) each tie appears at the end of each woman's preference list. The current best lower bounds on the approximation ratio for this variant are 1.1052 unless P=NP and 1.25 under the unique games conjecture, while the current best upper bound is 1.4616. In this paper, we improve the upper bound to 1.25, which matches the lower bound under the unique games conjecture. Note that this is the first special case of the MAX SMTI where the tight approximation bound is obtained. The improved ratio is achieved via a new analysis technique, which avoids the complicated case-by-case analysis used in earlier studies. As a by-product of our analysis, we show that the integrality gap of natural IP and LP formulations for this variant is 1.25. We also show that the unrestricted MAX SMTI cannot be approximated with less than 1.5 unless the approximation ratio of a certain special case of the minimum maximal matching problem can be improved.

LA eng

DO 10.4230/LIPIcs.APPROX-RANDOM.2015.361

LK http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.361

OL 30