Cseh Ágnes és szerzőtársai cikke az Algorithmica folyóiratban

Matchings with Lower Quotas: Algorithms and Complexity címmel megjelent Cseh Ágnes tudományos munkatárs és Ashwin Arulselvan, Martin Groß, David F. Manlove, valamint Jannik Matuschke közös cikke az Algorithmica folyóiratban.

Abstract

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph G=(A˙P,E)G=(A∪˙P,E) with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NPNP-hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota umaxumax as basis, and we prove that this dependence is necessary unless FPT=W[1]FPT=W[1]. The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee umax+1umax+1, which is asymptotically best possible unless P=NPP=NP. Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.

 

 

  • Események

    • KTI szeminárium – Békés Gábor 2019.02.21.

      2019.02.21.
      2019.02.21.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K0.13-14 Békés Gábor, Bisztray Márta: Területi egyensúly – a munkaerőpiac és az ingatlanárak kapcsolata Magyarországon  A dolgozat célja annak felderítése, hogy a területi egyensúlyi modell ...   Részletek »

    • KTI szeminárium – Simonovits András 02.28.

      2019.02.28.
      2019.02.28.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K0.11-12 Simonovits András: Hagymahántás közben: a rugalmas nyugdíjkorhatár modelljei Az öregedő társadalmak nyugdíjgondjainak megoldásában az egyik leghatékonyabb eszköz az átlagos nyugdíjkorhatár (az ún. korcentrum) emelése. Ehhez ...   Részletek »

    • KTI szeminárium – Cseh Ágnes 03.07.

      2019.03.07.
      2019.03.07.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K0.11-12 Cseh Ágnes: Organizing Time Banks: Lessons from Matching Markets társszerzők: T. Andersson, L. Ehlers, and A. Erlanson A time bank is a group of ...   Részletek »

  • Hírek

    • Az MTA KRTK Közgazdaság-tudományi Intézet teljesítményéről

      2018.09.12.

      Az MTA KRTK Közgazdaság-tudományi Intézet teljesítményéről Az MTA KRTK KTI a RePEc/IDEAS rangsorában, amely a világ közgazdaságtudományi tanszékeit és intézeteit rangsorolja publikációs teljesítményük alapján, ...   Részletek »

    • MTA KRTK állásfoglalás

      2018.06.20.

      Tisztelt Kollégák! Tudományos kutatóként, intézeti vezetőként egész életünkben a kutatói szabadság és felelősség elve vezetett bennünket. Meggyőződésünk, hogy a tudomány csak akkor érhet el ...   Részletek »

    • 2019. február 18.

      2019.02.18.

      Közgazdaságtan a neoliberalizmus után – S. Naidu, D. Rodrik, G. Zucman Economics After Neoliberalism SURESH NAIDU, DANI RODRIK, GABRIEL ZUCMAN Boston Review – February ...   Részletek »

    • 2019. február 11.

      2019.02.11.

      D. McCloskey interjúja – E. Wallach An Interview with Deidre McCloskey, Distinguished Professor Emerita of Economics and of History, UIC Eric Wallach February 10, ...   Részletek »

    • Az MTA KRTK Közalkalmazotti Tanácsának értesítése

      2019.02.10.

      Értesítés 2019. február 6-án az MTA KRTK Közalkalmazotti Tanácsa az MTA Közgazdaság- és Regionális Tudományi Kutatóközpont intézeteinek valamennyi közalkalmazottjára kiterjedő elektronikus szavazást kezdeményezett az ...   Részletek »

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