IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v22y2011i3d10.1007_s10878-009-9287-9.html
   My bibliography  Save this article

Popular matchings: structure and algorithms

Author

Listed:
  • Eric McDermid

    (University of Glasgow)

  • Robert W. Irving

    (University of Glasgow)

Abstract

An instance of the popular matching problem (POP-M) consists of a set of applicants and a set of posts. Each applicant has a preference list that strictly ranks a subset of the posts. A matching M of applicants to posts is popular if there is no other matching M′ such that more applicants prefer M′ to M than prefer M to M′. Abraham et al. (SIAM J. Comput. 37:1030–1045, 2007) described a linear time algorithm to determine whether a popular matching exists for a given instance of POP-M, and if so to find a largest such matching. A number of variants and extensions of POP-M have recently been studied. This paper provides a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a structure called the switching graph, a directed graph computable in linear time from the preference lists. We show that the switching graph can be exploited to yield efficient algorithms for a range of associated problems, including the counting and enumeration of the set of popular matchings, generation of a popular matching uniformly at random, finding all applicant-post pairs that can occur in a popular matching, and computing popular matchings that satisfy various additional optimality criteria. Our algorithms for computing such optimal popular matchings improve those described in a recent paper by Kavitha and Nasre (Proceedings of MATCH-UP: Matching Under Preferences—Algorithms and Complexity, 2008).

Suggested Citation

  • Eric McDermid & Robert W. Irving, 2011. "Popular matchings: structure and algorithms," Journal of Combinatorial Optimization, Springer, vol. 22(3), pages 339-358, October.
    • Handle: RePEc:spr:jcomop:v:22:y:2011:i:3:d:10.1007_s10878-009-9287-9
    DOI: 10.1007/s10878-009-9287-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-009-9287-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-009-9287-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Agnes Cseh & Telikepalli Kavitha, 2017. "Popular Edges and Dominant Matchings," CERS-IE WORKING PAPERS 1725, Institute of Economics, Centre for Economic and Regional Studies.
    2. Kondratev, Aleksei Y. & Nesterov, Alexander S., 2022. "Minimal envy and popular matchings," European Journal of Operational Research, Elsevier, vol. 296(3), pages 776-787.
    3. Agnes Cseh & Chien-Chung Huang & Telikepalli Kavitha, 2017. "Popular matchings with two-sided preferences and one-sided ties," CERS-IE WORKING PAPERS 1723, Institute of Economics, Centre for Economic and Regional Studies.
    4. Naoyuki Kamiyama, 2016. "The popular matching and condensation problems under matroid constraints," Journal of Combinatorial Optimization, Springer, vol. 32(4), pages 1305-1326, November.
    5. Bettina Klaus & David F. Manlove & Francesca Rossi, 2014. "Matching under Preferences," Cahiers de Recherches Economiques du Département d'économie 14.07, Université de Lausanne, Faculté des HEC, Département d’économie.
    6. Aleksei Yu. Kondratev & Alexander S. Nesterov, 2018. "Random Paths to Popularity in Two-Sided Matching," HSE Working papers WP BRP 195/EC/2018, National Research University Higher School of Economics.
    7. Telikepalli Kavitha & Meghana Nasre & Prajakta Nimbhorkar, 2014. "Popularity at minimum cost," Journal of Combinatorial Optimization, Springer, vol. 27(3), pages 574-596, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:22:y:2011:i:3:d:10.1007_s10878-009-9287-9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.