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

dc.contributor.authorFekete, Sándor P.
dc.contributor.authorMeijer, Henk
dc.contributor.authorRohe, André
dc.contributor.authorTietze, Walter
dc.date.accessioned2021-12-17T10:17:32Z
dc.date.available2021-12-17T10:17:32Z
dc.date.issued2000
dc.description.abstractWe 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.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15953
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14726
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.othermaximum weight matchingen
dc.subject.otherFermat-Weber problemen
dc.subject.otherapproximationen
dc.subject.otherheuristicen
dc.subject.otherplanar point setsen
dc.subject.otherdualityen
dc.subject.othermaximum Traveling Salesman Problemen
dc.titleSolving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problemsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2000, 695en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090C27 Combinatorial optimizationen
tub.subject.msc200090C59 Approximation methods and heuristicsen

Files

Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-695-2000.pdf
Size:
12.95 MB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Report-695-2000.ps
Size:
459.08 KB
Format:
Postscript Files

Collections