Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems
<|reference_start|>Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems: 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 relationship 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.<|reference_end|>
@article{fekete2002solving,
    title={Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for
  Maximum Matchings and Maximum Traveling Salesman Problems},
    author={Sandor P. Fekete, Henk Meijer, Andre Rohe, and Walter Tietze},
    journal={Journal of Experimental Algorithms, 7 (2002), article 11.},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0212044},
    primaryClass={cs.DS}
}