Sándor P. Fekete
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 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.
Supplemental Material
Available for Download
- AHUJA, R., MAGNANTI, T., AND ORLIN, J. 1993. Network flows. Theory, algorithms and applications. Prentice-Hall, New-York.]] Google Scholar
Digital Library
- APPLEGATE, D., BIXBY, R., CHVÁTAL, V., AND COOK, W. 1998. On the solution of traveling salesman problems. Documenta Mathematica Extra Volume Proceedings ICM III (1998), 645-656.]]Google Scholar
- ARORA, S. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM 45, 5, 753-782.]] Google ScholarDigital Library
- BAJAJ, C. 1988. The algebraic degree of geometric optimization problems. Discrete Comput. Geom. 3, 177-191.]]Google ScholarDigital Library
- BARVINOK, A. I., FEKETE, S. P., JOHNSON, D. S., TAMIR, A., WOEGINGER, G. J., AND WOODROOFE, R. 2002. The geometric maximum traveling salesman problem. http://arxiv.org/abs/cs.DS/0204024.]]Google Scholar
- BARVINOK, A. I., JOHNSON, D. S., WOEGINGER, G. J., AND WOODROOFE, R. 1998. The maximum traveling salesman problem under polyhedral norms. In Proceedings of the 6th International Conference on Integer Programming and Combinatorial Optimization (IPCO), Volume 1412 of Lecture Notes in Computer Science (1998), pp. 195-201. Springer-Verlag.]]Google ScholarCross Ref
- BOYD, S. C. AND PULLEYBLANK, W. R. 1990/1991. Optimizing over the subtour polytope of the travelling salesman problem. Mathematical Programming 49(2), 163-187.]]Google ScholarDigital Library
- COOK, W. AND ROHE, A. 1999. Computing minimum-weight perfect matchings. INFORMS Journal on Computing 11, 138-148.]]Google ScholarCross Ref
- EDMONDS, J. 1965a. Maximum matching and a polyhedron with 0,1 vertices. J. Res. Nat. Bur. Standards (B) 69, 125-130.]]Google ScholarCross Ref
- EDMONDS, J. 1965b. Paths, trees, and flowers. Canad. J. Math. 17, 449-467.]]Google ScholarCross Ref
- FEKETE. 1999. Simplicity and hardness of the maximum traveling salesman problem under geometric distances. In Proceedings of SODA 1999: ACM-SIAM Symposium on Discrete Algorithms (1999), pp. 337-345.]] Google ScholarDigital Library
- FEKETE, S. P. AND MEIJER, H. 2000. On minimum stars, minimum Steiner stars, and maximum matchings. Discrete and Computational Geometry 23, 340a, 389-407.]]Google Scholar
- FEKETE, S. P., MEIJER, H., ROHE, A., AND TIETZE, W. 2001. Solving a "hard" problem to approximate an "easy" one: Heuristics for maximum matchings and maximum traveling salesman problems. In Proceedings of the Third International Workshop on Algorithm Engineering and Experiments (ALENEX), Volume 2153 of Lecture Notes in Computer Science (2001), pp. 1-16. Springer-Verlag.]] Google ScholarDigital Library
- GABOW, H. 1990. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (1990), pp. 434-443. ACM Press.]] Google ScholarDigital Library
- HELD, M. AND KARP, R. M. 1971. The traveling salesman problem and minimum spanning trees: Part ii. Mathematical Programming 1, 6-25.]]Google ScholarDigital Library
- JOHNSON, D. S. AND PAPADIMITRIOU, C. H. 1985. Computational complexity. In E. L. LAWLER, J. K. LENSTRA, A. H. G. R. KAN, AND D. B. SHMOYS Eds., The traveling salesman problem, Chapter 3, pp. 37-85. Chichester: Wiley.]]Google Scholar
- KUHN, H. W. 1973. A note on Fermat's problem. Math. Programming 4, 98-107.]]Google ScholarCross Ref
- MEHLHORN, K. AND SCHÄFER, G. 2000. Implementation of o(nm log n) weighted matchings in general graphs: The power of data structures. In Proceedings of the 3rd Workshop on Algorithm Engineering, Volume 1982 of Lecture Notes in Computer Science (2000), pp. 23-38. Springer-Verlag.]] Google ScholarDigital Library
- MITCHELL, J. S. B. 1999. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing 28, 4, 1298-1309.]] Google ScholarDigital Library
- REINELT, G. 1991. TSPLIB: A traveling salesman problem library. ORSA Journal on Computing, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ 3, 376-384.]]Google Scholar
- RICHTER-GEBERT, J. AND KORTENKAMP, U. 1999. The Interactive Geometry Software Cinderella. Springer-Verlag, Heidelberg.]] Google ScholarDigital Library
- ROHE, A. 1997. Parallele Heuristiken für sehr große Traveling Salesman Probleme. Master's thesis, Universität Bonn.]]Google Scholar
- TAMIR, A. AND MITCHELL, J. S. B. 1998. A maximum b-matching problem arising from median location models with applications to the roommates problem. Math. Programming 80, 171-194.]] Google ScholarDigital Library
- VAIDYA, P. M. 1989. Geometry helps in matching. SIAM J. Comput. 18, 6, 1201-1225.]] Google ScholarDigital Library
- VALENZUELA, C. L. AND JONES, A. J. 1997. Estimating the Held-Karp lower bound for the geometric TSP. European Journal of Operational Research 102, 157-175.]]Google ScholarCross Ref
- VARADARAJAN, K. R. 1998. A divide-and-conquer algorithm for min-cost perfect matching in the plane. In IEEE Symposium on Foundations of Computer Science (1998), pp. 320-331.]] Google ScholarDigital Library
- WEISZFELD, E. 1937. Sur le point pour lequel la somme des distances de n points donnés est minimum. Tôhoku Math. J. 43, 355-386.]]Google Scholar
Index Terms
- Solving a "Hard" problem to approximate an "Easy" one: heuristics for maximum matchings and maximum traveling salesman problems
Recommendations
Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems
ALENEX '01: Revised Papers from the Third International Workshop on Algorithm Engineering and ExperimentationWe 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-...
Heuristics for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem
This paper deals with a generalisation of the well-knowntraveling salesman problem (TSP) in which cities correspond to customers providing or requiring known amounts of a product, and the vehicle has a given upper limit capacity. Each customer must be ...
Doubly-rooted stem-and-cycle ejection chain algorithm for the asymmetric traveling salesman problem
Ejection chain methods, which include the classical Lin-Kernighan LK procedure and the Stem-and-Cycle S&C reference structure, have been the source of the currently leading algorithms for large scale symmetric traveling salesman problems STSP. Although ...
Comments