Computer Science – Data Structures and Algorithms
Scientific paper
2002-12-16
Journal of Experimental Algorithms, 7 (2002), article 11.
Computer Science
Data Structures and Algorithms
20 pages, 14 figures, Latex, to appear in Journal of Experimental Algorithms, 2002
Scientific paper
We consider geometric instances of the Maximum Weighted Matching Problem (MWMP) and the Maximum Traveling Salesman Problem (MTSP) with up to 3,000,000 vertices. Making use of a geometric duality relationship between MWMP, MTSP, and the Fermat-Weber-Problem (FWP), we develop a heuristic approach that yields in near-linear time solutions as well as upper bounds. Using various computational tools, we get solutions within considerably less than 1% of the optimum. An interesting feature of our approach is that, even though an FWP is hard to compute in theory and Edmonds' algorithm for maximum weighted matching yields a polynomial solution for the MWMP, the practical behavior is just the opposite, and we can solve the FWP with high accuracy in order to find a good heuristic solution for the MWMP.
Fekete Sandor P.
Meijer Henk
Rohe Andre
Tietze Walter
No associations
LandOfFree
Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-426456