Let $G = (X\cup Y, E)$ be a bipartite graph. Suppose $X$ contains people, $Y$ contains seats in a theatre, and each edge $(x,y)$ has a weight representing how much person $x$ is willing to pay for seat $y$. The goal is to find a maximum-weight matching (to maximize the total profit).

But now there are social distancing constraints: if some seat $y_k$ is matched, then seats $y_{k+1}$ and $y_{k-1}$ must remain unmatched. Is there a polynomial-time algorithm for finding a maximum-weight matching?


  1. In the special case in which $|Y|=2|X|-1$ and we also require the matching to also have maximum cardinality, we must match only the odd-indexed vertices of $Y$, so the problem reduces to simple maximum-weight matching. But I am interested in maximum weight matching, and in the general case in which $|Y|$ may be arbitrary.

  2. Suppose all weights are 0 or 1. Without social distancing, the graph can be converted into a flow-network by adding a source node before $X$, adding a sink node after $Y$, and making the capacity of all edges equal to 1. Then, an integral flow corresponds to a matching. But I do not see how to convert the social distancing constraints to flow constraints.

  3. A common technique for finding a maximum-cardinality mathcing is to iteratively apply augmenting paths. But here, an augmenting path might break the distance constraint.

  4. Another common technique is to solve a linear program with a variable $z_{x,y}$ for each pair $x\in X, y\in Y$. Without distance constraints, the problem is to maximize $\sum_{x\in X, y\in Y} w_{x,y} z_{x,y}$ subject to the following constraints:

  • $\sum_{y \in Y} z_{x,y} \leq 1$ for all $x \in X$
  • $\sum_{x \in X} z_{x,y} \leq 1$ for all $y \in Y$
  • $0 \leq z_{x,y}\leq 1$ for all $x \in X$ and $y \in Y $

The constraint matrix is known to be totally-unimodular, so an integer solution exists. But With gaps, we have to replace the second set of constraints with:

  • $\sum_{x \in X} [z_{x,y} + z_{x,y+1}] \leq 1$ for all $y \in Y$

and I do not know whether the resulting matrix is totally-unimodular.

Is anything else known about this problem?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.