hello,
could anyone help me by suggesting a good approximation algorithm for minimum weight perfect matching on graphs? I can't seem to find anything that makes any sense! i'm trying to implement Christofides algorithm for the travelling salesman problem in java but i'm stuck at the perfect matching bit. any help would be greatly appreciated.
thanks,
eoin
eoin 0 Newbie Poster
koren6
I am facing the same problem!
Please contact me if you found a solution...
Thanks
Chainsaw 12 Posting Pro in Training
Did you try google? I typed into google "minimum weight perfect matching" and got a ton of answers, including this one which looks like what you want. Keep Google as one of your best tools for research!
http://www.algorithmic-solutions.info/leda_guide/graph_algorithms/weighted_perfect_matching.html
abhiengi 0 Newbie Poster
hello,
could anyone help me by suggesting a good approximation algorithm for minimum weight perfect matching on graphs? i'm trying to implement Christofides algorithm for the travelling salesman problem in R but i'm stuck at the perfect matching bit. any help would be greatly appreciated.
thanks,
abhinay
kpm3uw 0 Newbie Poster
Minimum weight perfect matching comes up in quantum computing when dealing with the error correcting code called the toric code. There is an approximation which uses renormalization ideas from physics by Guillaume Duclos-Cianci and David Poulin. The basic idea is to use different scales to match vertices. Frist split your grid up into squares of length 2. If you can match vertices in the square, do so. Otherwise iterate and make the length scale 4,8,16,etc... and continue matching. This is the skeleton of the algorithm but the actual algorithm has a lot of caveats that you'll have to read about or figure out for yourself or else you can use this idea of different scales to invent your own algorithm. I believe that the time compelixty is like log(l), parallelized compared l^6 for min weight perfect matching.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.