AI Chat AI Image Generator AI Video Text to Speech

Approximating Stable Matchings with Ties of Bounded Size

05/11/2020

∙

by Jochen Koenemann, et al.

∙

∙

Finding a stable matching is one of the central problems in algorithmic game theory. If participants are allowed to have ties and incomplete preferences, computing a stable matching of maximum cardinality is known to be NP-hard. In this paper we present a (3L-2)/(2L-1)-approximation algorithm for the stable matching problem with ties of size at most L and incomplete lists. Our result matches the known lower bound on the integrality gap for the associated LP formulation.

Jochen Koenemann
8 publications
Kanstantsin Pashkovich
12 publications
Natig Tofigzade
2 publications

research

∙ 05/11/2020

On the Approximability of the Stable Matching Problem with Ties of Constant Size up to the Integrality Gap

Finding a stable matching is one of the central problems in algorithmic ...

0 Jochen Koenemann, et al. ∙

research

∙ 08/14/2018

On the approximability of the stable matching problem with ties of size two

The stable matching problem is one of the central problems of algorithmi...

0 Robert Chiang, et al. ∙

research

∙ 10/05/2018

Mathematical models for stable matching problems with ties and incomplete lists

We present new integer linear programming (ILP) models for NP-hard optim...

0 Maxence Delorme, et al. ∙

research

∙ 05/14/2018

On the approximability of the stable marriage problem with one-sided ties

The classical stable marriage problem asks for a matching between a set ...

0 Felix Bauckholt, et al. ∙

research

∙ 02/15/2019

Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists

In the stable marriage problem (SM), a mechanism that always outputs a s...

0 Koki Hamada, et al. ∙

research

∙ 11/21/2019

Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters

We continue and extend previous work on the parameterized complexity ana...

0 Robert Bredereck, et al. ∙

research

∙ 06/28/2019

Stable Matchings in Divorce Graphs

In this paper, we study the Reaching Stable Marriage via Divorce Operati...

0 Jiehua Chen, et al. ∙