Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems
dc.contributor.author | Fekete, Sándor P. | |
dc.contributor.author | Meijer, Henk | |
dc.contributor.author | Rohe, André | |
dc.contributor.author | Tietze, Walter | |
dc.date.accessioned | 2021-12-17T10:17:32Z | |
dc.date.available | 2021-12-17T10:17:32Z | |
dc.date.issued | 2000 | |
dc.description.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. | en |
dc.identifier.issn | 2197-8085 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15953 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14726 | |
dc.language.iso | en | en |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
dc.subject.ddc | 510 Mathematik | en |
dc.subject.other | maximum weight matching | en |
dc.subject.other | Fermat-Weber problem | en |
dc.subject.other | approximation | en |
dc.subject.other | heuristic | en |
dc.subject.other | planar point sets | en |
dc.subject.other | duality | en |
dc.subject.other | maximum Traveling Salesman Problem | en |
dc.title | Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems | en |
dc.type | Research Paper | en |
dc.type.version | submittedVersion | en |
tub.accessrights.dnb | free | en |
tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
tub.affiliation.institute | Inst. Mathematik | de |
tub.publisher.universityorinstitution | Technische Universität Berlin | en |
tub.series.issuenumber | 2000, 695 | en |
tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
tub.subject.msc2000 | 90C27 Combinatorial optimization | en |
tub.subject.msc2000 | 90C59 Approximation methods and heuristics | en |