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

**Harvard**

Huang, C. och Kavitha, T. (2015) *Improved approximation algorithms for two variants of the stable marriage problem with ties*.

** BibTeX **

@article{

Huang2015,

author={Huang, Chien-Chung and Kavitha, T.},

title={Improved approximation algorithms for two variants of the stable marriage problem with ties},

journal={Mathematical programming},

issn={0025-5610},

volume={154},

issue={1-2},

pages={353-380},

abstract={We consider the problem of computing a large stable matching in a bipartite graph where each vertex ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M(u). A matching M is said to be stable if there is no edge (a, b) such that a is unmatched or prefers b to M(a) and similarly, b is unmatched or prefers a to M(b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that computing a maximum size stable matching is APX-hard. In this paper we first consider the case when the preference lists of vertices in A are strict while the preference lists of vertices in B may include ties. This case is also APX-hard and the current best approximation ratio known here is 25/17 which relies on solving an LP. We improve this ratio to 22/15 by a simple linear time algorithm. Here we first compute a half-integral stable matching in and then round it to an integral stable matching M. The ratio is bounded via a payment scheme that charges other components in to cover the costs of length-5 augmenting paths. There will be no length-3 augmenting paths here. We next consider the following special case of two-sided ties, where every tie length is 2. This case is known to be UGC-hard to approximate to within 4/3. We show a 10/7 approximation algorithm here that runs in linear time.},

year={2015},

keywords={Stable matching, Approximation algorithms},

}

** RefWorks **

RT Journal Article

SR Electronic

ID 229991

A1 Huang, Chien-Chung

A1 Kavitha, T.

T1 Improved approximation algorithms for two variants of the stable marriage problem with ties

YR 2015

JF Mathematical programming

SN 0025-5610

VO 154

IS 1-2

SP 353

OP 380

AB We consider the problem of computing a large stable matching in a bipartite graph where each vertex ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M(u). A matching M is said to be stable if there is no edge (a, b) such that a is unmatched or prefers b to M(a) and similarly, b is unmatched or prefers a to M(b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that computing a maximum size stable matching is APX-hard. In this paper we first consider the case when the preference lists of vertices in A are strict while the preference lists of vertices in B may include ties. This case is also APX-hard and the current best approximation ratio known here is 25/17 which relies on solving an LP. We improve this ratio to 22/15 by a simple linear time algorithm. Here we first compute a half-integral stable matching in and then round it to an integral stable matching M. The ratio is bounded via a payment scheme that charges other components in to cover the costs of length-5 augmenting paths. There will be no length-3 augmenting paths here. We next consider the following special case of two-sided ties, where every tie length is 2. This case is known to be UGC-hard to approximate to within 4/3. We show a 10/7 approximation algorithm here that runs in linear time.

LA eng

DO 10.1007/s10107-015-0923-0

LK http://dx.doi.org/10.1007/s10107-015-0923-0

OL 30