0
$\begingroup$

The subject of this question are perfect matchings of a complete undirected graph $G(V,E), n:=\mathrm{card}(V)=2k$, without self-loops or parallel edges and $n=2k$ vertices.

The objective is to determine a perfect matching $\mathrm{M}_{\text{opt}}$ of minimal weight.

Consider now the greedy heuristic that determines a perfect matching $\mathrm{M}_{\text{app}}$ by starting with $\mathrm{M}_{\text{app}}\,=\,\emptyset$ and keeps adding the shortest edge that is not adjacent to any edge in $\mathrm{M}_{\text{app}}$ until it is a perfect matching.

Question:

Is it true, that the longest edge in $\mathrm{M}_{\text{opt}}$ can't be strictly longer than the longest edge in $\mathrm{M}_{\text{app}}$?

I am convinced that that must be true for the following reason: if $\mathrm{M}_{\text{opt}}$ contains a longer edge, then it must also contain an edge that compensates for the weight difference and is not contained in $\mathrm{M}_{\text{app}}$.
As the shortest edge is already contained in $\mathrm{M}_{\text{app}}$ it can't be the edge that compensates for the weight difference; therefore it must be adjacent to some shorter edge in $\mathrm{M}_{\text{app}}$, which completes the proof; is that actually the case?


If the longest edge of $\mathrm{M}_{\text{opt}}$ can't indeed be longer than the longest edge of $\mathrm{M}_{\text{app}}$ the performance of matching algorithms could in some cases be improved substantially by reducing the number of candidate edges

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Let the weights of the edges in a 6-cycle in $K_6$ be $1,2,5,6,5,2$ (in cyclic order), and let other weights be large. Then the optimal matching will be $2,2,6$, while the greedy one will consist of $1,5,5$.

A similar construction works with longer cycles.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .