Dartmouth College Computer Science Technical Report series CS home TR home TR search TR listserv By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Bounded Unpopularity Matchings
Chien-Chung Huang, Kavitha Telikepalli, Dimitrios Michail, Meghana Nasre
Dartmouth TR2008-616

Abstract:

We investigate the following problem: given a set of jobs and a set of people with preferences over the jobs, what is the optimal way of matching people to jobs? Here we consider the notion of \emph{popularity}. A matching $M$ is popular if there is no matching $M'$ such that more people prefer $M'$ to $M$ than the other way around. Determining whether a given instance admits a popular matching and, if so, finding one, was studied in \cite{AIKM05}. If there is no popular matching, a reasonable substitute is a matching whose {\em unpopularity} is bounded. We consider two measures of unpopularity - {\em unpopularity factor} denoted by $u(M)$ and {\em unpopularity margin} denoted by $g(M)$. McCutchen recently showed that computing a matching $M$ with the minimum value of $u(M)$ or $g(M)$ is NP-hard, and that if $G$ does not admit a popular matching, then we have $u(M) \ge 2$ for all matchings $M$ in $G$.

Here we show that a matching $M$ that achieves $u(M) = 2$ can be computed in $O(m\sqrt{n})$ time (where $m$ is the number of edges in $G$ and $n$ is the number of nodes) provided a certain graph $H$ admits a matching that matches all people. We also describe a sequence of graphs: $H = H_2, H_3,\ldots,H_k$ such that if $H_k$ admits a matching that matches all people, then we can compute in $O(km\sqrt{n})$ time a matching $M$ such that $u(M) \le k-1$ and $g(M) \le n(1-\frac{2}{k})$. Simulation results suggest that our algorithm finds a matching with low unpopularity.

PDF (116KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
Chien-Chung Huang, Kavitha Telikepalli, Dimitrios Michail, and Meghana Nasre, "Bounded Unpopularity Matchings." Dartmouth Computer Science Technical Report TR2008-616, April 2008.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.