MathOverflow Asked on December 25, 2020

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.

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.

Answered by Nathan Lindzey on December 25, 2020

Let binary variable $x_e$ indicate whether $ein M$. The usual maximum weighted matching problem is to maximize $sum_e c_e x_e$ subject to: $$sum_{ein E: vin e} x_e le 1 quad text{for all $vin 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.

Answered by RobPratt on December 25, 2020

0 Asked on December 15, 2021 by inkspot

ag algebraic geometry reference request rt representation theory

1 Asked on December 15, 2021 by chris-ramsey

fa functional analysis linear algebra matrices oa operator algebras

5 Asked on December 13, 2021 by william-stagner

ct category theory ho history overview kt k theory and homology rt representation theory symmetric functions

1 Asked on December 13, 2021

1 Asked on December 13, 2021

2 Asked on December 13, 2021 by mirco-a-mannucci

0 Asked on December 13, 2021

1 Asked on December 13, 2021 by jdoe2

3 Asked on December 13, 2021 by ikp

0 Asked on December 13, 2021

1 Asked on December 13, 2021 by andi-bauer

ct category theory monoidal categories symmetric monoidal categories

1 Asked on December 13, 2021 by user45397

0 Asked on December 13, 2021

ca classical analysis and odes differential equations fa functional analysis real analysis rough paths

0 Asked on December 13, 2021

dg differential geometry geometric measure theory measure theory numerical analysis of pde oc optimization and control

2 Asked on December 13, 2021

1 Asked on December 11, 2021

fa functional analysis nuclear spaces short exact sequences tensor products

1 Asked on December 11, 2021

dg differential geometry lie groups random matrices rt representation theory st statistics

0 Asked on December 11, 2021

0 Asked on December 11, 2021 by titouan-vayer

1 Asked on December 11, 2021

foundations lo logic mathematical philosophy proof theory reference request

Get help from others!

Recent Answers

- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP