2026-07-21T14:16:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13266 2024-03-06T10:51:59Z ddc:004 open_access

Min-Cost Popular Matchings Kavitha, Telikepalli Bipartite graphs Stable matchings Dual certificates Let G = (A ∪ B, E) be a bipartite graph on n vertices where every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if there is no matching N such that vertices that prefer N to M outnumber those that prefer M to N. Popular matchings always exist in G since every stable matching is popular. Thus it is easy to find a popular matching in G - however it is NP-hard to compute a min-cost popular matching in G when there is a cost function on the edge set; moreover it is NP-hard to approximate this to any multiplicative factor. An O^*(2ⁿ) algorithm to compute a min-cost popular matching in G follows from known results. Here we show: - an algorithm with running time O^*(2^{n/4}) ≈ O^*(1.19ⁿ) to compute a min-cost popular matching; - assume all edge costs are non-negative - then given ε > 0, a randomized algorithm with running time poly(n,1/(ε)) to compute a matching M such that cost(M) is at most twice the optimal cost and with high probability, the fraction of all matchings more popular than M is at most 1/2+ε. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Telikepalli Kavitha 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.25 urn:nbn:de:0030-drops-132668 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.25 eng https://creativecommons.org/licenses/by/3.0/legalcode