IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v27y2021i3d10.1007_s10732-020-09464-8.html
   My bibliography  Save this article

A max-conflicts based heuristic search for the stable marriage problem with ties and incomplete lists

Author

Listed:
  • Hoang Huu Viet

    (Vinh University)

  • Nguyen Thi Uyen

    (Vinh University)

  • SeungGwan Lee

    (Kyung Hee University)

  • TaeChoong Chung

    (Kyung Hee University)

  • Le Hong Trang

    (Ho Chi Minh City University of Technology
    Vietnam National University - Ho Chi Minh City (VNU-HCM))

Abstract

In this paper, we propose a heuristic search algorithm based on maximum conflicts to find a weakly stable matching of maximum size for the stable marriage problem with ties and incomplete lists. The key idea of our approach is to define a heuristic function based on the information extracted from undominated blocking pairs from the men’s point of view. By choosing a man corresponding to the maximum value of the heuristic function, we aim to not only remove all the blocking pairs formed by the man but also reject as many blocking pairs as possible for an unstable matching from the women’s point of view to obtain a solution of the problem as quickly as possible. Experiments show that our algorithm is efficient in terms of both execution time and solution quality for solving the problem.

Suggested Citation

  • Hoang Huu Viet & Nguyen Thi Uyen & SeungGwan Lee & TaeChoong Chung & Le Hong Trang, 2021. "A max-conflicts based heuristic search for the stable marriage problem with ties and incomplete lists," Journal of Heuristics, Springer, vol. 27(3), pages 439-458, June.
    • Handle: RePEc:spr:joheur:v:27:y:2021:i:3:d:10.1007_s10732-020-09464-8
    DOI: 10.1007/s10732-020-09464-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-020-09464-8
    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/s10732-020-09464-8?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.

    References listed on IDEAS

    as
    1. Diebold, Franz & Bichler, Martin, 2017. "Matching with indifferences: A comparison of algorithms in the context of course allocation," European Journal of Operational Research, Elsevier, vol. 260(1), pages 268-282.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Biró, Péter & Gudmundsson, Jens, 2021. "Complexity of finding Pareto-efficient allocations of highest welfare," European Journal of Operational Research, Elsevier, vol. 291(2), pages 614-628.
    2. Ágoston, Kolos Csaba & Biró, Péter & Szántó, Richárd, 2018. "Stable project allocation under distributional constraints," Operations Research Perspectives, Elsevier, vol. 5(C), pages 59-68.
    3. Erdil, Aytek & Ergin, Haluk, 2017. "Two-sided matching with indifferences," Journal of Economic Theory, Elsevier, vol. 171(C), pages 268-292.
    4. Martin Bichler & Soeren Merting, 2021. "Randomized Scheduling Mechanisms: Assigning Course Seats in a Fair and Efficient Way," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3540-3559, October.
    5. Kondratev, Aleksei Y. & Nesterov, Alexander S., 2022. "Minimal envy and popular matchings," European Journal of Operational Research, Elsevier, vol. 296(3), pages 776-787.
    6. Delorme, Maxence & García, Sergio & Gondzio, Jacek & Kalcsics, Jörg & Manlove, David & Pettersson, William, 2019. "Mathematical models for stable matching problems with ties and incomplete lists," European Journal of Operational Research, Elsevier, vol. 277(2), pages 426-441.
    7. Li, Mengling, 2020. "Ties matter: Improving efficiency in course allocation by allowing ties," Journal of Economic Behavior & Organization, Elsevier, vol. 178(C), pages 354-384.
    8. Christian Haas, 2021. "Two-Sided Matching with Indifferences: Using Heuristics to Improve Properties of Stable Matchings," Computational Economics, Springer;Society for Computational Economics, vol. 57(4), pages 1115-1148, April.
    9. Gartner, Daniel & Kolisch, Rainer, 2021. "Mathematical programming for nominating exchange students for international universities: The impact of stakeholders’ objectives and fairness constraints on allocations," Socio-Economic Planning Sciences, Elsevier, vol. 76(C).
    10. Ágoston, Kolos Csaba & Biró, Péter & Kováts, Endre & Jankó, Zsuzsanna, 2022. "College admissions with ties and common quotas: Integer programming approach," European Journal of Operational Research, Elsevier, vol. 299(2), pages 722-734.
    11. Suresh P. Sethi & Sushil Gupta & Vipin K. Agrawal & Vijay K. Agrawal, 2022. "Nobel laureates’ contributions to and impacts on operations management," Production and Operations Management, Production and Operations Management Society, vol. 31(12), pages 4283-4303, December.
    12. Martin Bichler & Alexander Hammerl & Thayer Morrill & Stefan Waldherr, 2021. "How to Assign Scarce Resources Without Money: Designing Information Systems that are Efficient, Truthful, and (Pretty) Fair," Information Systems Research, INFORMS, vol. 32(2), pages 335-355, June.
    13. Daniel Kornbluth & Alexey Kushnir, 2024. "Undergraduate Course Allocation through Competitive Markets," Papers 2412.05691, arXiv.org.
    14. Karaenke, Paul & Bichler, Martin & Merting, Soeren & Minner, Stefan, 2020. "Non-monetary coordination mechanisms for time slot allocation in warehouse delivery," European Journal of Operational Research, Elsevier, vol. 286(3), pages 897-907.

    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:joheur:v:27:y:2021:i:3:d:10.1007_s10732-020-09464-8. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.