Thumbnail Image
🆕 Date Issued:
2000
🗄 In DepositOnce:2021-12-17
Submitted Version

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

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

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