A 1.875: approximation algorithm for the stable marriage problem

Kazuo Iwama · Shuichi Miyazaki · Naoya Yamauchi

64 citations0/0 files storedSymposium on Discrete Algorithms

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Voting Systems Complexity and Algorithms in Graphs Optimization and Search Problems

Abstract

We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. This problem is known to be APX-hard, and the current best known approximation algorithm achieves the approximation ratio 2-c 1/√N, where c is some positive constant. In this paper, we give a 1.875-approximation algorithm, which is the first result on the approximation ratio better than two.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 64 citations exist upstream.

References

1962College Admissions and the Stability of Marriage 1991The Stable Marriage Problem: Structure and Algorithms 1999Stable Marriage with Incomplete Lists and Ties 2005Pareto Optimality in House Allocation Problems 2003Approximability results for stable marriage problems with ties 2003Strong Stability in the Hospitals/Residents Problem

Cited by

2008Better and Simpler Approximation Algorithms for the Stable Marriage Problem

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.