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

An instance of the marriage problem is given by a graph G together with, for each vertex of G, a strict preference order over its neighbors. A matching M of G is popular in the marriage instance if M does not lose a head-to-head election against any matching where vertices are voters. Every...

We are given a bipartite graph G = (A B;E) where each vertex has a preference list ranking its neighbors: in particular, every a A ranks its neighbors in a strict order of preference, whereas the preference list of any b B may contain ties. A matching M is popular if there is no matching M' such...

We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists (SRI) that are degree constrained, i.e., preference lists are of bounded length. The first variant, egal d-SRI, involves finding an egalitarian stable matching in solvable...