Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other edge $e'$ in $M$. That is, the edge weight depends on the matching we choose. How to approach this problem? Clearly when $w(e,e')=0$ for any pair of $(e,e')$, the problem degenerates to standard max weight matching.
2
-
$\begingroup$ Do I understand correctly that the weight assigned to matching M is sum_{e in M} (sum_{e' in M} w(e,e'))? $\endgroup$– Louigi Addario-BerryCommented May 28, 2020 at 0:37
-
$\begingroup$ Thank you Louigi. Yes, we can formulate in this way. $\endgroup$– lchenCommented May 28, 2020 at 9:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Let binary variable $x_e$ indicate whether $e\in M$. The usual maximum weighted matching problem is to maximize $\sum_e c_e x_e$ subject to: $$\sum_{e\in E: v\in e} x_e \le 1 \quad \text{for all $v\in V$}$$
To model your variant, introduce nonnegative variable $y_{e,e'}$ for each pair $e<e'$ of edges, change the objective to maximize $\sum_e c_e x_e + \sum_{e<e'} w(e,e')y_{e,e'}$, and impose constraints: $$x_e + x_{e'} - 1 \le y_{e,e'}$$ Note that $y_{e,e'}$ will automatically be integer-valued even without explicitly defining it to be binary.
-
$\begingroup$ Thank you Rob. Let me be more specific. I seek answers or references to the following questions: (1) is my problem NP-hard? (2) how to design polynomial algorithm or approximate algorithm with constant factor to solve it? $\endgroup$– lchenCommented May 22, 2020 at 8:36
$\begingroup$
$\endgroup$
I'm assuming that by maximal we actually mean maximum.
A rainbow perfect matching in a (not necessarily proper) edge-colored bipartite graph $G$ on $2n$ vertices is a perfect matching of $G$ such that no two edges have the same color.
Let $G = (V,E)$ be an edge-colored bipartite graph on $2n$ vertices. Let $w(\cdot)$ be the all-ones function, and define $w(\cdot,\cdot)$ such that $w(e,e') = 0$ if $e,e' \in E$ are a pair of disjoint edges that have different colors; otherwise, $w(e,e') = -c$ for any $c > 0$. An algorithm that solves your problem outputs $n$ if and only if $G$ has a rainbow perfect matching.
The rainbow perfect matching problem for bipartite graphs is NP-Complete (see, for example, Theorem 1 in Van Bang Le, Florian Pfender, Complexity results for rainbow matchings, Theoretical Computer Science, Volume 524, 2014).
I don't have a hardness of approximation proof, but I am skeptical that your problem admits a polynomial-time constant-factor approximation algorithm. It seems very close to the quadratic assignment problem, and such problems are hard to approximate in polynomial time within a constant factor in both theory and practice.
