direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 695-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems
Authors
Sándor P. Fekete, Henk Meijer, André Rohe, and Walter Tietze
Publication
Submitted for publication
Classification
MSC:
primary: 90C27 Combinatorial optimization
secondary: 90C59 Approximation methods and heuristics
Keywords
maximum weight matching, Fermat-Weber problem, approximation, heuristic, planar point sets, duality, maximum Traveling Salesman Problem.
Abstract
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.
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.
Source
Download as [PDF] [ps.gz] [ps.Z] [ps]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe