Thumbnail Image
🆕 Date Issued:
2000
🗄 Date Available:2021-12-17
Research Paper

Please use this identifier to cite or link to this item:

Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems

Fekete, Sándor P.; Meijer, Henk; Rohe, André; Tietze, Walter

Inst. Mathematik

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 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.
maximum weight matchingFermat-Weber problemapproximationheuristicplanar point setsdualitymaximum Traveling Salesman Problem
In Copyright
Full item page