Geometric TSP on sets

DOI10.4230/LIPICS.ISAAC.2023.6MaRDI QIDQ6953215zbMATH OpenFDO

Authors Mark de Berg

Publication date 24 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2023.6

zbMATH Keywords

Euclidean TSPrectilinear TSPTSP on neighbourhoodsTSP on sets

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• A PTAS for TSP with neighborhoods among fat regions in the plane
• An ETH-tight exact algorithm for Euclidean TSP
• Approximation algorithms for generalized MST and TSP in grid clusters
• Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
• Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
• Geometric separator theorems and applications
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• On the complexity of k-SAT
• Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
• The Euclidean traveling salesman problem is NP-complete
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• TSP with neighborhoods of varying size

This page was built for publication: Geometric TSP on sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6953215)