Matchings with lower quotas: Algorithms and complexity

Ashwin Arulselvan (ashwin.arulselvan@strath.ac.uk), Agnes Cseh (cseh.agnes@krtk.mta.hu), Martin Groß (gross@math.tu-berlin.de), David F. Manlove (david.manlove@glasgow.ac.uk) and Jannik Matuschke (jannik.matuschke@tum.de)
Additional contact information
Ashwin Arulselvan: Department of Management Science, Sir William Duncan Building, University of Strathclyde
Agnes Cseh: Institute of Economics, Research Centre for Economic and Regional Studies, Hungarian Academy of Sciences, and Corvinus University of Budapest
Martin Groß: Institute for Mathematics, Technische Universität Berlin
David F. Manlove: School of Computing Science, Sir Alwyn Williams Building, University of Glasgow
Jannik Matuschke: TUM School of Management, Technische Universiät München

No 1724, CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies

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) 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, xedparameter tractability, as well as approximability. We draw the line between NP-hard and polynomially tractable instances in terms of degree and quota constraints and provide ecient 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 umax as basis, and we prove that this dependence is necessary unless FPT = W[1]. The approximability of wmlq is also discussed: we present an approximation algorithm for the general case with performance guarantee umax + 1, which is asymptotically best possible unless P = NP. Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.

Keywords: maximum matching; many-to-one matching; project allocation; inapproximability; bounded treewidth (search for similar items in EconPapers)
JEL-codes: C63 C78 (search for similar items in EconPapers)
Pages: 29 pages
Date: 2017-09
New Economics Papers: this item is included in nep-cmp, nep-gth and nep-ppm
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://econ.core.hu/file/download/mtdp/MTDP1724.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to econ.core.hu:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:has:discpr:1724

Access Statistics for this paper

More papers in CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies Contact information at EDIRC.
Bibliographic data for series maintained by Nora Horvath (horvath.nora@krtk.mta.hu this e-mail address is bad, please contact repec@repec.org).