Popular critical matchings in the many-to-many setting

DOI10.1016/J.TCS.2023.114281MaRDI QIDQ6199405zbMATH OpenOpenAlexFDO

Authors Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan

Publication date 23 February 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.12394

zbMATH Keywords

criticallower quotasmany-to-manymatchingpopulartwo-sided preferences

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We consider the many-to-many bipartite matching problem in the presence of two-sided preferences and two-sided lower quotas. The input to our problem is a bipartite graph G=(A U B, E), where each vertex in A U B specifies a strict preference ordering over its neighbors. Each vertex has an upper quota and a lower quota denoting the maximum and minimum number of vertices that can be assigned to it from its neighborhood. In the many-to-many setting with two-sided lower quotas, informally, a critical matching is a matching which fulfils vertex lower quotas to the maximum possible extent. This is a natural generalization of the definition of critical matching in the one-to-one setting [Kavitha T., FSTTCS 2021]. Our goal in the given problem is to find a popular matching in the set of critical matchings. A matching is popular in a given set of matchings if it remains undefeated in a head-to-head election with any matching in that set. Here, vertices cast votes between pairs of matchings. We show that there always exists a matching that is popular in the set of critical matchings. We present an efficient algorithm to compute such a matching of the largest size. We prove the popularity of our matching using a dual certificate.

Cites work

• A matroid approach to stable matchings with lower quotas
• A new approach to the maximum-flow problem
• A Size-Popularity Tradeoff in the Stable Marriage Problem
• College Admissions and the Stability of Marriage
• Connections in combinatorial optimization
• Envy-free matchings with lower quotas
• Envy-freeness and relaxed stability: hardness and approximation algorithms
• Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas
• Many-to-one popular matchings with two-sided preferences and one-sided ties
• Pareto optimality in many-to-many matching problems
• Popular branchings and their dual certificates
• Popular Matchings
• Popular matchings in the marriage and roommates problems
• Popular matchings in the stable marriage problem
• Popular matchings with two-sided preferences and one-sided ties
• Popularity in the generalized hospital residents setting
• Popularity, Mixed Matchings, and Self-Duality
• Quasi-popular Matchings, Optimality, and Extended Formulations
• Simple push-relabel algorithms for matroids and submodular flows
• Stability and Polarization of Interests in Job Matching
• Stable matchings with covering constraints: a complete computational trichotomy
• Strongly stable assignment
• The hospitals/residents problem with lower quotas
• The lattice of envy-free matchings
• Two problems in max-size popular matchings
• Understanding popular matchings via stable matchings

Cited in

(2)

• Max-utility matchings with popularity via critical vertices
• Many-to-many polygon matching à la Jaccard

This page was built for publication: Popular critical matchings in the many-to-many setting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199405)