How to Secure General Acceptance for a Matching? - Inverse Popular Matchings
Erika Bérczi-Kovács, Eszter Szabó
Source abstract
Inverse optimization problems focus on minimizing the adjustments made to the input data to achieve a desired outcome. Popular matchings are relaxations of stable matchings that prioritize the overall welfare of society over individual preferences. In this work, we aim to determine a minimum cost set of nodes in order to make a given matching popular by updating preferences at the chosen set. We show that the problem is NP-hard, even if the input matching is perfect or the graph is bipartite. If the desired matching is maximum size in the graph, we present a polynomial time algorithm to determine this minimum in bipartite graphs, and provide a dual characterization.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.