A structural approach to matching problems with preferences

QA75 Electronic computers. Computer science

McDermid, Eric J. ; Irving, Robert W.

University:University of Glasgow

Department:School of Computing Science

关键词: stable matching, hospitals/residents, approximation algorithm, graph, lattice, partially ordered set, preference, fairness, one-sided matching, Gallai-Edmonds decomposition theorem, indifference, ties, bipartite graph, exponential-time algorithm, couples;   

Others  :  http://theses.gla.ac.uk/2371/1/2010mcdermidphd.pdf

来源: University of Glasgow

【 摘 要 】

This thesis is a study of a number of matching problems that seek to match together pairs or groups of agents subject to the preferences of some or all of the agents. We present a number of new algorithmic results for five specific problem domains.Each of these results is derived with the aid of some structural properties implicitly embedded in the problem.We begin by describing an approximation algorithm for the problem of finding amaximum stable matching for an instance of the stable marriage problem with ties and incomplete lists (MAX-SMTI). Our polynomial time approximation algorithm provides a performance guarantee of 3/2 for the general version of MAX-SMTI, improvingupon the previous best approximation algorithm, which gave a performance guarantee of 5/3.Next, we study thesex-equal stable marriage problem (SESM).We show that SESM is W[1]-hard, even if the men's and women's preference lists are both of length at most three.This improves upon the previously known hardness results.We contrast this with an exact, low-order exponential time algorithm.This is the first non-trivial exponential time algorithm known for this problem, or indeed for any hard stable matching problem. Turning our attention to the hospitals / residents problem with couples (HRC), we show that HRC is NP-complete, even if very severe restrictions are placed on the input.By contrast, we give a linear-time algorithm to find a stable matching with couples (or report that none exists) when stability is defined in terms of the classical Gale-Shapley concept.This result represents the most general polynomial time solvable restriction of HRC that we are aware of. We then explore the three dimensional stable matching problem (3DSM), in which we seek to find stable matchingsacross three sets of agents, rather than two (as in the classical case).We show that under two natural definitions of stability, finding a stable matching for a 3DSM instance is NP-complete.These hardness results resolve some open questions in the literature.Finally, we study the popular matching problem (POP-M) in the context of matching a set of applicants to a set of posts.We provide a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a new structure called the switching graph exploited to yield efficient algorithms for a range of associated problems, extending and improving upon the previously best-known results for this problem.