Name
Abstract | ||
|---|---|---|
Let G = (A boolean OR P, E) be a bipartite graph where A denotes a set of agents, P denotes a set of posts and ranks on the edges denote preferences of the agents over posts. A matching M in G is rank-maximal if it matches the maximum number of applicants to their top-rank post, subject to this, the maximum number of applicants to their second rank post and so on. In this paper, we develop a switching graph characterization of rank-maximal matchings, which is a useful tool that encodes all rank-maximal matchings in an instance. The characterization leads to simple and efficient algorithms for several interesting problems. In particular, we give an efficient algorithm to compute the set of rank-maximal pairs in an instance. We show that the problem of counting the number of rank-maximal matchings is # P-Complete and also give an FPRAS for the problem. Finally, we consider the problem of deciding whether a rank-maximal matching is popular among all the rank-maximal matchings in a given instance, and give an efficient algorithm for the problem. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-13075-0_47 | ALGORITHMS AND COMPUTATION, ISAAC 2014 |
DocType | Volume | ISSN |
Journal | 8889 | 0302-9743 |
Citations | PageRank | References |
1 | 0.37 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pratik Ghoshal | 1 | 2 | 1.08 |
| Meghana Nasre | 2 | 1 | 0.37 |
| Prajakta Nimbhorkar | 3 | 170 | 15.04 |