CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

An improved approximation algorithm for the stable marriage problem with one-sided ties

Chien-Chung Huang (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; T. Kavitha
Lecture Notes in Computer Science - 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO, Bonn, Germany, 23-25 June 2014 (0302-9743). Vol. 8494 (2014), p. 297-308.
[Konferensbidrag, refereegranskat]

We consider the problem of computing a large stable matching in a bipartite graph G = (A ∪ B, E) where each vertex u εA ∪ B ranks its neighbors in an order of preference, perhaps involving ties. 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 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 ≈ 1.4706 which relies on solving an LP. We improve this ratio to 22/15 ≈ 1.4667 by a simple linear time algorithm. We first compute a half-integral stable matching in {0,0.5,1}|E| and round it to an integral stable matching M. The ratio |OPT|/|M| is bounded via a payment scheme that charges other components in OPT ⊕ M to cover the costs of length-5 augmenting paths. There will be no length-3 augmenting paths here. We also 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 ≈ 1.4286 approximation algorithm here that runs in linear time.

Nyckelord: Approximation algorithms, Combinatorial optimization, Integer programming, Best approximations, Bipartite graphs, Gale-shapley algorithms, Linear-time algorithms, Payment schemes, Preference lists, Stable marriage problem, Stable matching

Denna post skapades 2015-05-05. Senast ändrad 2016-04-15.
CPL Pubid: 216425


Läs direkt!

Länk till annan sajt (kan kräva inloggning)