Optimal popular matchings |
| |
Authors: | Telikepalli Kavitha Meghana Nasre |
| |
Affiliation: | aIndian Institute of Science, Bangalore, India |
| |
Abstract: | In this paper we consider the problem of computing an “optimal” popular matching. We assume that our input instance admits a popular matching and here we are asked to return not any popular matching but an optimal popular matching, where the definition of optimality is given as a part of the problem statement; for instance, optimality could be fairness in which case we are required to return a fair popular matching. We show an O(n2+m) algorithm for this problem, assuming that the preference lists are strict, where m is the number of edges in G and n is the number of applicants. |
| |
Keywords: | Design of algorithms Bipartite graphs Matchings One-sided preference lists |
本文献已被 ScienceDirect 等数据库收录! |