  We study a natural generalization of the maximum weight many-to-one matching
problem. We are given an undirected bipartite graph $G= (A \cup 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 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 $u_{max}$ 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 $u_{\max}+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.
