Many-to-one matchings with lower quotas: algorithms and complexity

Ashwin Arulselvan, Ágnes Cseh, Martin Groß, David F. Manlove, Jannik Matuschke

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

2 Citations (Scopus)
62 Downloads (Pure)

Abstract

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph G = (AUP,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-toone 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-toone 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 classic polynomial time algorithms, fixed-parameter 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 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 umax as basis, and we prove that this dependence is necessary unless FPT = W[1]. Finally, we also present an approximation algorithm for the general case with performance guarantee umax+1, which is asymptotically best possible unless P = NP.

Original languageEnglish
Title of host publicationAlgorithms and Computation
Subtitle of host publication26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings
Place of PublicationBerlin
PublisherSpringer-Verlag
Pages176-187
Number of pages12
Volume9472
ISBN (Print)9783662489703
DOIs
Publication statusPublished - 27 Nov 2015
Event26th International Symposium on Algorithms and Computation, ISAAC 2015 - Nagoya, Japan
Duration: 9 Dec 201511 Dec 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume9472
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Symposium on Algorithms and Computation, ISAAC 2015
CountryJapan
CityNagoya
Period9/12/1511/12/15

Keywords

  • maximum matching
  • many-to-one matching
  • project allocation
  • inapproximability
  • bounded treewidth

Fingerprint Dive into the research topics of 'Many-to-one matchings with lower quotas: algorithms and complexity'. Together they form a unique fingerprint.

Cite this