Buchumschlag

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

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kisfaludi-Bak, Sándor, Marx, Dániel
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms Computational Geometry
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2020)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
von: de Berg, Mark, et al.
Veröffentlicht: (2026)

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

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

Faster Approximation Scheme for Euclidean $k$-TSP
von: van Wijland, Ernest, et al.
Veröffentlicht: (2023)

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

Touring a Sequence of Orthogonal Polygons
von: Casel, Katrin, et al.
Veröffentlicht: (2026)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2020)

Structure and Independence in Hyperbolic Uniform Disk Graphs
von: Bläsius, Thomas, et al.
Veröffentlicht: (2024)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2025)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
von: Duraj, Lech, et al.
Veröffentlicht: (2023)

On Approximability of Steiner Tree in $\ell_p$-metrics
von: Fleischmann, Henry, et al.
Veröffentlicht: (2023)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2026)

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

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
von: Bhore, Sujoy, et al.
Veröffentlicht: (2024)

Balanced TSP partitioning
von: Berendsohn, Benjamin Aram, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Smallest Intersecting Balls
von: Zheng, Jiaqi, et al.
Veröffentlicht: (2024)

Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
von: Banik, Aritra, et al.
Veröffentlicht: (2025)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
von: Abbasi, Fateme, et al.
Veröffentlicht: (2023)

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

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

Online sorting and online TSP: randomized, stochastic, and high-dimensional
von: Abrahamsen, Mikkel, et al.
Veröffentlicht: (2024)

The Complexity of Geodesic Spanners using Steiner Points
von: de Berg, Sarita, et al.
Veröffentlicht: (2024)

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

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
von: Grandoni, Fabrizio, et al.
Veröffentlicht: (2026)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2024)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
von: Banik, Aritra, et al.
Veröffentlicht: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2024)

Parameterized Geometric Graph Modification with Disk Scaling
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Counting Unit Circular Arc Intersections
von: Wang, Haitao
Veröffentlicht: (2026)

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

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
von: Ren, Kinter, et al.
Veröffentlicht: (2024)

Improved Hardness of Approximation for Geometric Bin Packing
von: Ray, Arka, et al.
Veröffentlicht: (2023)

Lower bounds for the universal TSP on the plane
von: Kravaris, Cosmas
Veröffentlicht: (2024)

Parameterized Approximation of Rectangle Stabbing
von: Chu, Huairui, et al.
Veröffentlicht: (2026)

Maximum Matchings in Geometric Intersection Graphs
von: Bonnet, Édouard, et al.
Veröffentlicht: (2019)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
von: Yang, Puhan, et al.
Veröffentlicht: (2025)

Reconstructing Riemannian Metrics From Random Geometric Graphs
von: Huang, Han, et al.
Veröffentlicht: (2025)

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

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
von: Gaudio, Julia, et al.
Veröffentlicht: (2026)