Tata Institute of Fundamental Research
Minimizing the Number of Unhappy Singles: An Improved Approximation Algorithm for the Stable Marriage Problem With One-sided Ties
Seminar
Speaker:
Chien-Chung Huang (Chalmers University
Department of Computer Science and Engineering
Gothenburg
Sweden)
Organiser:
Kavitha Telikepalli
Date:
Friday, 13 Jun 2014, 11:30 to 12:30
Venue:
AG-80
(Scan to add to calendar)
Abstract:
Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A U B, E) where each vertex ranks its neighbors in an order of preference, perhaps involving ties.The goal is to compute a large stable matching. It is known that computing a maximum size stable matching is APX-hard. We present an improved approximation algorithm for the case when ties are present only in the preference lists of vertices in B. This case is also APX-hard and the current best approximation ratio known here is 25/17, we show a simple linear time algorithm that achieves an approximation ratio of 22/15.
| Speaker: | Chien-Chung Huang (Chalmers University Department of Computer Science and Engineering Gothenburg Sweden) |
| Organiser: | Kavitha Telikepalli |
| Date: | Friday, 13 Jun 2014, 11:30 to 12:30 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A U B, E) where each vertex ranks its neighbors in an order of preference, perhaps involving ties.The goal is to compute a large stable matching. It is known that computing a maximum size stable matching is APX-hard. We present an improved approximation algorithm for the case when ties are present only in the preference lists of vertices in B. This case is also APX-hard and the current best approximation ratio known here is 25/17, we show a simple linear time algorithm that achieves an approximation ratio of 22/15.