Name
Abstract | ||
|---|---|---|
We consider the problem of matching applicants to posts where applicants have preferences over posts. Thus the input to our problem is a bipartite graph \(G=(\mathcal {A}\cup \mathcal {P},E)\), where \(\mathcal {A}\) denotes a set of applicants, \(\mathcal {P}\) is a set of posts, and there are ranks on edges which denote the preferences of applicants over posts. A matching M in G is called rank-maximal if it matches the maximum number of applicants to their rank 1 posts, subject to this the maximum number of applicants to their rank 2 posts, and so on. We consider this problem in a dynamic setting, where vertices and edges can be added and deleted at any point. Let n and m be the number of vertices and edges in an instance G, and r be the maximum rank used by any rank-maximal matching in G. We give a simple \(O(r(m+n))\)-time algorithm to update an existing rank-maximal matching under each of these changes. When \(r=o(n)\), this is faster than recomputing a rank-maximal matching completely using a known algorithm like that of Irving et al. (ACM Trans Algorithms 2(4):602–610, 2006), which takes time \(O(\min ((r+n,r\sqrt{n})m)\). Our algorithm can also be used for maintaining a popular matching in the one-sided preference model in \(O(m+n)\) time, whenever one exists. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s10878-018-0348-9 | J. Comb. Optim. |
Keywords | Field | DocType |
Rank-maximal matching, Augmenting path, Rank, Preferences, Popular matching | Combinatorics,Vertex (geometry),Bipartite graph,Mathematics | Journal |
Volume | Issue | ISSN |
37 | 2 | 1573-2886 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prajakta Nimbhorkar | 1 | 170 | 15.04 |
| Arvind Rameshwar V | 2 | 0 | 0.34 |