Cseh Ágnes és Telikepalli Kavitha cikke a Mathematical Programming folyóiratban

Cseh Ágnes tudományos munkatárs és Telikepalli Kavitha közös cikke Popular edges and dominant matchings címmel megjelent a Mathematical programming folyóiratban.

Abstract

Given a bipartite graph G=(A∪B,E) with strict preference lists and given an edge e∗∈E , we ask if there exists a popular matching in G that contains e∗ . We call this the popular edge problem. A matching M is popular if there is no matching M′ such that the vertices that prefer M′ to M outnumber those that prefer M to M′ . It is known that every stable matching is popular; however G may have no stable matching with the edge e∗ . In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge e∗ , then there is either a stable matching that contains e∗ or a dominant matching that contains e∗ . This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an O(n3) algorithm to find a popular matching containing a given set of edges or report that none exists, where n=|A|+|B| .

  • Események

    • KTI szeminárium : Halpern 70 conference

      2021.06.17.
      13:00 - 15:00

      Helyszín: Az előadást hibrid formában tartjuk meg : a személyes részvétel mellett (helyszín : KRTK Közgazdaságtudományi Intézet, 1097 Budapest, Tóth Kálmán u. 4., K11-K12 terem) zoomon keresztül is be lehet kapcsolódni. Az ehhez tartozó link külső érdeklődők számára a kti.titkarsag@krtk.hu e-mail címen igényelhető és csütörtök délután válik elérhetővé. Kérjük, részvételi szándékukat legkésőbb június 10-ig jelezzék. Preliminary programme 1 pm – 1.05 pm Short introduction 1.05 pm – 2.20 pm Presentations 1 (15 minute presentations, 15 minute discussion in the ...   Read More »

  • Hírek

Felhasználási feltételek
Impresszum
Intézményünk országos ésnemzetközi hálózati kapcsolatátaz NIIF program biztosítja
Közgazdaság- és Regionális Tudományi Kutatóközpont Közgazdaság-tudományi Intézet
© Copyright 2020. Minden jog fenntartva.