A ( $2-c\frac{1}{\sqrt{N}}$ )-Approximation Algorithm for the Stable Marriage Problem

Autor:	Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi
Rok vydání:	2007
Předmět:	Combinatorics Current (mathematics) General Computer Science Matching (graph theory) Applied Mathematics Theory of computation Vertex cover Bipartite graph Approximation algorithm Stable marriage problem Constant (mathematics) Computer Science Applications Mathematics
Zdroj:	Algorithmica. 51:342-356
ISSN:	1432-0541 0178-4617
Popis:	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 NP-hard and the current best known approximation algorithm achieves the approximation ratio 2−c(log N)/N, where c is an arbitrary positive constant and N is the number of men in an input. In this paper, we improve the ratio to $2-c/\sqrt{N}$, where c is an arbitrary constant that satisfies $c\leq 1/{(4\sqrt{6})}$.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::49681cd9f9f996c2b4c565687fd9445c https://doi.org/10.1007/s00453-007-9101-y Zobrazit plný text záznamu Full text from SpringerLink