Cover Image

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kisfaludi-Bak, Sándor, Marx, Dániel
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
by: Chan, Timothy M., et al.
Published: (2026)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

Touring a Sequence of Orthogonal Polygons
by: Casel, Katrin, et al.
Published: (2026)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
by: Antoniadis, Antonios, et al.
Published: (2020)

Structure and Independence in Hyperbolic Uniform Disk Graphs
by: Bläsius, Thomas, et al.
Published: (2024)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2025)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
by: Duraj, Lech, et al.
Published: (2023)

On Approximability of Steiner Tree in $\ell_p$-metrics
by: Fleischmann, Henry, et al.
Published: (2023)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2026)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
by: Bhore, Sujoy, et al.
Published: (2024)

Balanced TSP partitioning
by: Berendsohn, Benjamin Aram, et al.
Published: (2025)

Approximation Algorithms for Smallest Intersecting Balls
by: Zheng, Jiaqi, et al.
Published: (2024)

Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
by: Banik, Aritra, et al.
Published: (2025)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
by: Galby, Esther, et al.
Published: (2023)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

Online sorting and online TSP: randomized, stochastic, and high-dimensional
by: Abrahamsen, Mikkel, et al.
Published: (2024)

The Complexity of Geodesic Spanners using Steiner Points
by: de Berg, Sarita, et al.
Published: (2024)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
by: Kar, Debajyoti, et al.
Published: (2026)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
by: Bartlmae, Simon, et al.
Published: (2024)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
by: Banik, Aritra, et al.
Published: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)

Parameterized Geometric Graph Modification with Disk Scaling
by: Fomin, Fedor V., et al.
Published: (2024)

Counting Unit Circular Arc Intersections
by: Wang, Haitao
Published: (2026)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
by: Ren, Kinter, et al.
Published: (2024)

Improved Hardness of Approximation for Geometric Bin Packing
by: Ray, Arka, et al.
Published: (2023)

Lower bounds for the universal TSP on the plane
by: Kravaris, Cosmas
Published: (2024)

Parameterized Approximation of Rectangle Stabbing
by: Chu, Huairui, et al.
Published: (2026)

Maximum Matchings in Geometric Intersection Graphs
by: Bonnet, Édouard, et al.
Published: (2019)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
by: Yang, Puhan, et al.
Published: (2025)

Reconstructing Riemannian Metrics From Random Geometric Graphs
by: Huang, Han, et al.
Published: (2025)

An Algorithmic Solution for Computing Circle Intersection Areas and its Applications to Wireless Communications
by: Librino, Federico, et al.
Published: (2012)

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
by: Gaudio, Julia, et al.
Published: (2026)