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.
