5
$\begingroup$

Context: After creating the minimum spanning tree, the next step in Christofides' TSP algorithm is to find all the N vertices with odd degree and find a minimum weight perfect matching for these odd vertices. N is even, so a bipartite matching is possible.

When the N odd-degree vertices are found, there are $n \choose \frac{n}{2}$ possible ways to split them into two sets. Does Christofides' algorithm really need to run a min-weight bipartite matching for all of these possible partitions? Or is there a better way?

I realize there is an approximate solution, which is to greedily match each vertex with another vertex that is closest to it. However, if the exact solution is to try all possible partitions, this seems inefficient.

Improve this question
$\endgroup$
1
  • $\begingroup$ Usually when we talk about approximation algorithms, we are considering only efficient (polytime) algorithms. This one is no exception. $\endgroup$
    – Yuval Filmus
    Commented Oct 31, 2015 at 9:14

2 Answers 2

Reset to default
3
$\begingroup$

There is the Blossom algorithm by Edmonds that determines a maximal matching for a weighted graph.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The standard blossom algorithm is applicable to a non-weighted graph. The last section on the wiki page says that the Blossom algorithm is only a subroutine if the goal is to find a min-weight or max-weight maximal matching on a weighted graph, and that a combinatorial algorithm needs to encapsulate the blossom algorithm. I haven't read the Kolmogorov paper yet, but the word "combinatorial" suggests that each possible partition of $N$ into two halves must be checked to get the min or max matching. $\endgroup$
    – yjc
    Commented Oct 30, 2015 at 19:22
  • $\begingroup$ The Kolmogorov paper references an overview paper (W. Cook and A. Rohe. Computing minimum-weight perfect matchings). In that paper the weighted version is also attributed to Edmonds: "Edmonds’ algorithm is based on a linear-programming formulation of the minimum-weight perfect-matching problem." But, alas, I am not a specialist in this algorithm. $\endgroup$
    – Hendrik Jan
    Commented Oct 30, 2015 at 22:46
  • $\begingroup$ That sounds promising, I'll have to study that algorithm, thanks for the reference. $\endgroup$
    – yjc
    Commented Oct 31, 2015 at 1:31
  • $\begingroup$ Combinatorial means that it operates in a discrete way. There are several polytime algorithms for minimum matching. $\endgroup$
    – Yuval Filmus
    Commented Oct 31, 2015 at 9:12
0
$\begingroup$

The blossom algorithm can be used to find a minimal matching of an arbitrary graph. It's nicer to use than a bipartite matching algorithm on all possible bipartitions, and will always find a minimal perfect matching in the TSP case.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Welcome to CS.SE! I'm not sure what this adds over the existing answer. Can I encourage you to take a look at some of our unanswered questions and see if you can contribute a useful answer to them? $\endgroup$
    – D.W. ♦
    Commented Mar 23, 2018 at 15:49
  • $\begingroup$ After reading the existing answer, it wasn't clear to me why the blossom algorithm was useful in this case, so I thought I'd elaborate. I don't have enough rep to edit/comment on the existing answer. Feel free to delete this answer - I just thought the extra comments would be useful for the next dummy like me that is struggling with the same problem. $\endgroup$
    – uozuAho
    Commented Mar 24, 2018 at 22:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.