@article{Fekete_Keldenich_Krupke_Niehs_2024, title={Edge Sparsification for Geometric Tour Problems}, volume={3}, url={https://cgt-journal.org/index.php/cgt/article/view/20}, DOI={10.57717/cgt.v3i1.20}, abstractNote={<div class="page" title="Page 1">
<div class="layoutArea">
<div class="column">
<p>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.</p>
<p>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.</p>
</div>
</div>
</div>}, number={1}, journal={Computing in Geometry and Topology}, author={Fekete, Sándor and Keldenich, Phillip and Krupke, Dominik and Niehs, Eike}, year={2024}, month={Jan.}, pages={1:1–1:23} }