2023/03/22 by Nasre, Meghana, Nimbhorkar, Prajakta, Ranjan, Keshav
#05C85 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2303.12325
We study the many-to-many bipartite matching problem in the presence of preferences where ties, as well as lower quotas, may appear on both sides of the bipartition. The input is a bipartite graph G=(A ∪ B, E), where each vertex in A ∪ B has a positive upper quota and a non-negative lower quota denoting the maximum and minimum number of vertices that can be assigned to it from its neighborhood. Additionally, each vertex specifies a preference ordering, possibly containing ties, over its neighbors. A critical matching is a matching which fulfills vertex lower quotas to the maximum possible extent. We seek to compute a matching that is critical as well as optimal with respect to the preferences of vertices. Stability, a well-accepted notion of optimality in the presence of two-sided preferences, is generalized to weak-stability in the presence of ties. However, a matching that is critical as well as weakly stable may not exist. Popularity is another well-investigated notion of optimality for the two-sided preference model; however, in the presence of ties (even without lower quotas), a popular matching may not exist. We, therefore, consider the notion of relaxed stability, which was introduced and studied by Krishnaa, Limaye, Nasre, and Nimbhorkar~(JoCO 2023). We show that a critical matching that is relaxed stable always exists, although computing a maximum-size relaxed stable matching turns out to be NP-hard. Our main contribution is a (3)/(2)-approximation algorithm for computing a maximum-size critical relaxed stable matching.