Edge Sparsification for Geometric Tour Problems
We study a variety of sparsification approaches for a spectrum of geometric optimization problems related to tour problems, such as the Angular TSP, the Minimum Perimeter Problem, and the Minimum/Maximum Area Polygon Problem. To this end, we conduct a thorough study that compares the solution quality and runtime achieved by integer programming solvers on geometrically reduced edge sets to the exact solution on the full edge set; considered sparsification techniques include a variety of triangulations (Delaunay, Greedy, Minimum Weight), Theta and Yao graphs, Well-Separated Pair Decomposition, and Onion graphs.
We demonstrate that edge sparsification often leads to significantly reduced runtimes. For several of the considered problems, we can compute within a few seconds solutions that are very close to being optimal for instances that could not be solved to provable optimality within an hour; for other problems, we encounter a significant loss in solution quality. However, for almost all problems we considered, we find good solutions much earlier in the search process than for the complete edge set; thus, our methods can at least be used to provide initial bounds for the exact solution, demonstrating their usefulness even if optimality cannot be established.
How to Cite
Copyright (c) 2024 Sándor Fekete, Phillip Keldenich, Dominik Krupke, Eike Niehs
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).