2018•arXiv (Cornell University)Open access

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

Robert Chiang, Kanstantsin Pashkovich

Abstract

The stable matching problem is one of the central problems of algorithmic\ngame theory. If participants are allowed to have ties, the problem of finding a\nstable matching of maximum cardinality is an NP-hard problem, even when the\nties are of size two. Moreover, in this setting it is UGC-hard to provide an\napproximation for the maximum cardinality stable matching problem with a\nconstant factor smaller than 4/3. In this paper, we give a tight analysis of an\napproximation algorithm given by Huang and Kavitha for the maximum cardinality\nstable matching problem with ties of size two, demonstrating an improved\n4/3-approximation factor.\n

Open-access reader

About this research paper

What this paper is about

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Key concepts: Cardinality (data modeling), Matching (statistics), Approximation algorithm, Mathematics, Combinatorics, Constant (computer programming), Stable marriage problem, Cardinal number (linguistics)