# 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 – Kristian Koerselman : Why Finnish polytechnics reject top applicants

2020.09.24.
14:00 - 16: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., K13-K14 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.mta.hu e-mail címen igényelhető és csütörtök délután válik elérhetővé. Abstract I use a panel of higher education clearinghouse data to study the centralized assignment of applicants to Finnish polytechnics. Many top applicants remain ...   Részletek »

• ## KTI szeminárium – Kaat Iterbeke (KU Leuven) : The Determinants of Peer Effects during Learning. Evidence from a Field Experiment

2020.10.01.
14:00 - 16:00

Helyszín: Az előadásra zoom felületen kerül sor 10.01-én 18:00 órakor. Az ehhez tartozó link külső érdeklődők számára a kti.titkarsag@krtk.mta.hu e-mail címen igényelhető és csütörtök délután válik elérhetővé. Abstract: In general, the paper aims to evaluate the effectiveness of an entrepreneurship education programme via a field experiment. In particular, the objectives of ...   Részletek »

• ## KTI szeminárium – Lindner Attila : Labor Supply and the Pension Contribution-Benefit Link

2020.10.08.
14:00 - 16: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–es 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.mta.hu e-mail címen igényelhető és csütörtök délután válik elérhetővé. We estimate the labor supply response to a reform that switched the Polish pension system from a Defined Benefit (DB) to a Notional Defined ...   Részletek »

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

• ## Megjelent az OECD új kiadványa Havas Attila szakértői közreműködésével

2020.09.11.

Optimising the operation and use of national research infrastructures This report is the outcome of a joint activity between Science Europe and the OECD, ...   Részletek »

• ## 2020. szeptember 11.

2020.09.11.

Shareholder vagy stakeholder kapitalizmus – 50 éve jelent meg M. Friedman cikke: a Promarket cikksorozatának bevezetője – L. Zingales Friedman’s Principle, 50 Years Later ...   Részletek »

• ## Megjelent Somogyi Róbert cikke a Mathematical Social Sciences tudományos folyóiratban

2020.09.10.

Bertrand–Edgeworth competition with substantial horizontal product differentiation Abstract Since Kreps and Scheinkman’s seminal article (1983) a large number of papers have analyzed capacity constraints’ ...   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
Közgazdaság- és Regionális Tudományi Kutatóközpont Közgazdaság-tudományi Intézet