# 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.

• ## KTI szeminárium – Szabó-Morvai Ágnes – habilitációs előadás -2022.01.27.

2022.01.27.
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élelőtt válik elérhetővé. Abstract: Educational Attainment and College Aspirations: The Role of Parental Preferences Two articles are presented in the topic of educational attainment and the role ...   Read More »

• ## KTI szeminárium : Karolina Vocke (Department of Economics, University of Inssbruck) – Stability in Large Markets

2022.02.03.
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élelőtt válik elérhetővé. Abstract In matching models, pairwise stable outcomes do not generally exist without substantial restrictions on both preferences and the topology of the network of ...   Read More »

• ## KTI szeminárium : Lengyel Balázs – Understanding hesitancy with revealed preferences across COVID-19 vaccine types

2022.02.10.
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élelőtt válik elérhetővé. ABSTRACT Many countries have secured larger quantities of COVID-19 vaccines than their populace is willing to take. This abundance and variety of vaccines created ...   Read More »

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

2020.05.07.

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

• ## 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 ...   Read More »

• ## Köllő János: Rövid jegyzet a munkanélküliség hosszáról

2022.01.21.

Az utóbbi hónapokban több határozott, de téves kijelentés kapott nagy sajtónyilvánosságot a munkanélküliség átlagos időtartamáról. Palkovics Imre, a Munkástanácsok elnöke szerint „egy átlag ...   Read More »

• ## Horn Dániel, Kiss Hubert János és Lénárd Tünde frissen megjelent tanulmányát ismerteti részletesen a Qubit

2022.01.19.

A NEMEK KÖZÖTTI KÜLÖNBSÉGEKET VIZSGÁLTÁK MAGYAR KAMASZOKON: A LÁNYOK ÖNZETLENEBBEK, A FIÚK VERSENGŐBBEK   Mit szeretnél inkább? Ma kapni 1000 forintot vagy két hét ...   Read More »

• ## Megjelentek Fertő Imre cikkei a Land Use Policy tudományos folyóiratban

2022.01.19.

The socioeconomic impacts of the CAP: Systematic literature review Abstract One of the main aims of the EU’s common agricultural policy (CAP) is to promote the ...   Read More »

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