Abstract | ||
---|---|---|
We consider an extension of the popular matching problem in this paper. The input to the popular matching problem is a bipartite graph $G = (\mathcal{A}\cup\mathcal{B},E)$ , where $\mathcal{A}$ is a set of people, $\mathcal{B}$ is a set of items, and each person $a \in\mathcal{A}$ ranks a subset of items in order of preference, with ties allowed. The popular matching problem seeks to compute a matching M 驴 between people and items such that there is no matching M where more people are happier with M than with M 驴. Such a matching M 驴 is called a popular matching. However, there are simple instances where no popular matching exists.Here we consider the following natural extension to the above problem: associated with each item $b \in\mathcal{B}$ is a non-negative price cost(b), that is, for any item b, new copies of b can be added to the input graph by paying an amount of cost(b) per copy. When G does not admit a popular matching, the problem is to "augment" G at minimum cost such that the new graph admits a popular matching. We show that this problem is NP-hard; in fact, it is NP-hard to approximate it within a factor of $\sqrt{n_{1}}/2$ , where n 1 is the number of people. This problem has a simple polynomial time algorithm when each person has a preference list of length at most 2. However, if we consider the problem of constructing a graph at minimum cost that admits a popular matching that matches all people, then even with preference lists of length 2, the problem becomes NP-hard. On the other hand, when the number of copies of each item is fixed, we show that the problem of computing a minimum cost popular matching or deciding that no popular matching exists can be solved in O(mn 1) time, where m is the number of edges. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/s10878-012-9537-0 | Clinical Orthopaedics and Related Research |
Keywords | Field | DocType |
Bipartite graphs,Matchings,One-sided preference lists,NP-hardness | Discrete mathematics,Combinatorics,Computer science,Popularity,Bipartite graph | Journal |
Volume | Issue | ISSN |
27 | 3 | 1382-6905 |
Citations | PageRank | References |
3 | 0.45 | 12 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Telikepalli Kavitha | 1 | 534 | 48.32 |
Meghana Nasre | 2 | 98 | 12.80 |
Prajakta Nimbhorkar | 3 | 170 | 15.04 |