Fekete, Sándor P.Meijer, HenkRohe, AndréTietze, Walter2021-12-172021-12-1720002197-8085https://depositonce.tu-berlin.de/handle/11303/15953http://dx.doi.org/10.14279/depositonce-14726We 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.en510 Mathematikmaximum weight matchingFermat-Weber problemapproximationheuristicplanar point setsdualitymaximum Traveling Salesman ProblemResearch Paper