Dynamic rank-maximal and popular matchings

Prajakta Nimbhorkar () and V. Arvind Rameshwar ()
Additional contact information
Prajakta Nimbhorkar: Chennai Mathematical Institute
V. Arvind Rameshwar: Indian Institute of Science

Journal of Combinatorial Optimization, 2019, vol. 37, issue 2, No 8, 523-545

Abstract: 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)$$ G = ( A ∪ P , E ) , where $$\mathcal {A}$$ A denotes a set of applicants, $$\mathcal {P}$$ 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))$$ O ( r ( m + n ) ) -time algorithm to update an existing rank-maximal matching under each of these changes. When $$r=o(n)$$ 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)$$ O ( min ( ( r + n , r n ) m ) . Our algorithm can also be used for maintaining a popular matching in the one-sided preference model in $$O(m+n)$$ O ( m + n ) time, whenever one exists.

Keywords: Rank-maximal matching; Augmenting path; Rank; Preferences; Popular matching (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0348-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:2:d:10.1007_s10878-018-0348-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0348-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().