9

The assignment problem is well-studied and has a nice polynomial time algorithm. I'm interested in an extension of this problem where all edges are in a certain group and taking multiple edges from the same group can end up with diminishing returns due to dependence on a shared resource. This means the edges are no longer independent and therefore it cannot be directly modeled as an assignment problem.

More formally, the problem is:

Given:

  • A weighted bipartite graph $G=(V,E)$ with weight function $w:E\rightarrow \mathbb{Q}$,

  • a "type set" $\mathcal{T}$ which partitions $E$ into groups that require the same resource. $T:E\rightarrow \mathcal{T}$ shows which type is associated with an edge.

  • A resource function $R: \mathcal{T}\times \mathbb{N}\rightarrow \mathbb{Q}$, decreasing in the second argument

Find a matching $M$ of $G$ and index $I:M\rightarrow \mathbb{N}$ that maximizes $$\sum_{e\in M} \min\{w(e), R(T(e),I(e))\},$$ where $I$ can use each value only once for each type (i.e. if $I(e)=I(e')$ and $e\neq e'$, then $T(e)\neq T(e')$).

Can this problem still be solved in polynomial time? If not, what would be a good alternative to model this, and why? Does this change if the number of types is a small constant (e.g. $<10$)?

Some observations:

I think it is possible to model this as an MILP, but that could take long even when the number of types is small. Still, it is possible that is the best we can do.

Also note that this is a special case of the 3-dimensional (weighted) matching problem, but that problem is very hard and modelling this in that way seems less promising than the MILP.

This question is inspired by an answer I gave here, which can be seen as an application of this problem.

Community
  • 1
Discrete lizard
  • 1,482
  • 6
  • 25
  • If you only ask for a matching, the problem is trivial in case $R$ and $w$ are positive. In the vanilla assignment problem, the task is to find a perfect matching of minimal total weight (or in its rectangular version, what is sometimes referred to as a full matching; i.e. one covering at least one of the partitions of the graph). Is that what you want here as well? – fuglede Aug 08 '19 at 17:52
  • @fuglede $R,w$ have positive range, yes. I'm not sure why you think the problem is trivial, can you elaborate? I am indeed looking for any matching, not necessarily a perfect one, but do note that I want to maximize the sum in this formulation. It could be that the usual assignment problem has minimization, I mostly "inherited" the maximisation formulation from the inspiration problem in the linked answer. – Discrete lizard Aug 08 '19 at 18:02
  • Gotcha; I did indeed erroneously read your "maximize" as a "minimize". – fuglede Aug 08 '19 at 18:05

0 Answers0