Name
Abstract | ||
|---|---|---|
In this paper, we consider the problem of computing an optimal matching in a bipartite graph where elements of one side of the bipartition specify preferences over the other side, and one or both sides can have capacities and classifications. The input instance is a bipartite graph G=(A U P,E), where A is a set of applicants, P is a set of posts, and each applicant ranks its neighbors in an order of preference, possibly involving ties. Moreover, each vertex v belonging to A U P has a quota q(v) denoting the maximum number of partners it can have in any allocation of applicants to posts -- referred to as a matching in this paper. A classification $mathcal{C}_u$ for a vertex $u$ is a collection of subsets of neighbors of $u$. Each subset (class) $Cin mathcal{C}_u$ has an upper quota denoting the maximum number of vertices from $C$ that can be matched to $u$. The goal is to find a matching that is optimal amongst all the feasible matchings, which are matchings that respect quotas of all the vertices and classes. consider two well-studied notions of optimality namely popularity and rank-maximality. We present an O(|E|^2)-time algorithm for finding a feasible rank-maximal matching, when each classification is a laminar family. We complement this with an NP-hardness result when classes are non-laminar even under strict preference lists, and even when only posts have classifications, and each applicant has a quota of one. show an analogous dichotomy result for computing a popular matching amongst feasible matchings (if one exists) where applicants having a quota of one. En-route to designing the polynomial time algorithms, we adapt the well-known Dulmage Mendelsohn decomposition of a bipartite graph w.r.t. a maximum matching to a maximum flow on special flow networks. We believe this generalization is of independent interest. |
Year | Venue | Field |
|---|---|---|
2018 | arXiv: Data Structures and Algorithms | Discrete mathematics,Combinatorics,Vertex (geometry),Optimal matching,Bipartite graph,Mathematics |
DocType | Volume | Citations |
Journal | abs/1805.02851 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meghana Nasre | 1 | 98 | 12.80 |
| Prajakta Nimbhorkar | 2 | 170 | 15.04 |
| Nada Pulath | 3 | 0 | 0.34 |