Document Open Access Logo

Min-Cost Popular Matchings

Author Telikepalli Kavitha

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.25.pdf
  • Filesize: 0.49 MB
  • 17 pages

Document Identifiers

Author Details

Telikepalli Kavitha
  • Tata Institute of Fundamental Research, Mumbai, India

Funding

We acknowledge support of the Department of Atomic Energy, Government of India, under project no. RTI4001.

Acknowledgements

Thanks to Jannik Matuschke for conversations on semi-popular matchings and to Piyush Srivastava for helpful discussions on sampling matchings. Thanks to the reviewers for their helpful comments.

Cite AsGet BibTex

Telikepalli Kavitha. Min-Cost Popular Matchings. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.25

Abstract

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+ε.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Bipartite graphs
  • Stable matchings
  • Dual certificates

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. Popular matchings. SIAM Journal on Computing, 37(4):1030-1045, 2007. Google Scholar
  2. P. Biro, R. W. Irving, and D. F. Manlove. Popular matchings in the marriage and roommates problems. In Proceedings of the seventh International Conference on Algorithms and Complexity (CIAC), pages 97-108, 2010. Google Scholar
  3. M.-J.-A.-N. de C. (Marquis de) Condorcet. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. L'Imprimerie Royale, 1785. Google Scholar
  4. Condorcet method. URL: https://en.wikipedia.org/wiki/Condorcet_method.
  5. Á. Cseh. Popular matchings. Trends in Computational Social Choice, Ulle Endriss (ed.), 2017. Google Scholar
  6. Á. Cseh, C.-C. Huang, and T. Kavitha. Popular matchings with two-sided preferences and one-sided ties. SIAM Journal on Discrete Mathematics, 31(4):2348-2377, 2017. Google Scholar
  7. Á. Cseh and T. Kavitha. Popular edges and dominant matchings. Mathematical Programming, 172(1):209-229, 2018. Google Scholar
  8. Y. Faenza and T. Kavitha. Quasi-popular matchings, optimality, and extended formulations. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 325-344, 2020. Google Scholar
  9. Y. Faenza, T. Kavitha, V. Powers, and X. Zhang. Popular matchings and limits to tractability. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2790-2809, 2019. Google Scholar
  10. T. Feder. A new fixed point approach for stable networks and stable marriages. Journal of Computer and System Sciences, 45(2):233-284, 1992. Google Scholar
  11. T. Feder. Network flow and 2-satisfiability. Algorithmica, 11(3):291-319, 1994. Google Scholar
  12. T. Fleiner. A fixed-point approach to stable matchings and some applications. Mathematics of Operations Research, 28(1):103-126, 2003. Google Scholar
  13. F. V. Fomin and D. Kratsch. Exact exponential algorithms. Springer-Verlag New York, Inc., New York, 2010. Google Scholar
  14. D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  15. D. Gale and M. Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11:223-232, 1985. Google Scholar
  16. P. Gärdenfors. Match making: assignments based on bilateral preferences. Behavioural Science, 20:166-173, 1975. Google Scholar
  17. S. Gupta, P. Misra, S. Saurabh, and M. Zehavi. Popular matching in roommates setting is np-hard. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2810-2822, 2019. Google Scholar
  18. M. Hirakawa, Y. Yamauchi, S. Kijima, and M. Yamashita. On the structure of popular matchings in the stable marriage problem - who can join a popular matching? In the 3rd International Workshop on Matching Under Preferences (MATCH-UP), 2015. Google Scholar
  19. C.-C. Huang and T. Kavitha. Popular matchings in the stable marriage problem. Information and Computation, 222:180-194, 2013. Google Scholar
  20. C.-C. Huang and T. Kavitha. Popularity, mixed matchings, and self-duality. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2294-2310, 2017. Google Scholar
  21. R. W. Irving, P. Leather, and D. Gusfield. An efficient algorithm for the "optimal" stable marriage. Journal of the ACM, 34(3):532-543, 1987. Google Scholar
  22. M. Jerrum and A. Sinclair. Approximating the permanent. SIAM Journal on Computing, 18(6):1149-1178, 1989. Google Scholar
  23. T. Kavitha. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43(1):52-71, 2014. Google Scholar
  24. T. Kavitha. Popular half-integral matchings. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 22:1-22:13, 2016. Google Scholar
  25. T. Kavitha. Popular roommates in simply exponential time. In Proceedings of the 39th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 20:1-20:15, 2019. Google Scholar
  26. T. Kavitha, J. Mestre, and M. Nasre. Popular mixed matchings. Theoretical Computer Science, 412:2679-2690, 2011. Google Scholar
  27. K. Makarychev, Y. Makarychev, M. Sviridenko, and J. Ward. A bi-criteria approximation algorithm for k-means. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 14:1-14:20, 2016. Google Scholar
  28. E. McDermid and R. W. Irving. Sex-equal stable matchings: Complexity and exact algorithms. Algorithmica, 68(3):545-570, 2014. Google Scholar
  29. U. G. Rothblum. Characterization of stable matchings as extreme points of a polytope. Mathematical Programming, 54:57-67, 1992. Google Scholar
  30. C.-P. Teo and J. Sethuraman. The geometry of fractional stable matchings and its applications. Mathematics of Operations Research, 23(4):874-891, 1998. Google Scholar
  31. J. H. Vande Vate. Linear programming brings marital bliss. Operations Research Letters, 8(3):147-153, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact