Cover Image

Faster Approximation Scheme for Euclidean $k$-TSP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	van Wijland, Ernest, Zhou, Hang
Format:	Preprint
Published:	2023
Subjects:	Computational Geometry Data Structures and Algorithms
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)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

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

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

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
by: Huang, Lingxiao, et al.
Published: (2022)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

On connections between k-coloring and Euclidean k-means
by: Aman, Enver, et al.
Published: (2024)

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)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

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)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

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

Space Complexity of Euclidean Clustering
by: Zhu, Xiaoyi, et al.
Published: (2024)

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

Data Structures for Approximate Discrete Fréchet Distance
by: van der Hoog, Ivor, et al.
Published: (2022)

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

Euclidean distance compression via deep random features
by: Leroux, Brett, et al.
Published: (2024)

Hybrid k-Clustering: Blending k-Median and k-Center
by: Fomin, Fedor V., et al.
Published: (2024)

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

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

Faster exponential algorithms for cut problems via geometric data structures
by: Kozma, László, et al.
Published: (2025)

Faster Goal-Oriented Shortest Path Search for Bulk and Incremental Detailed Routing
by: Ahrens, Markus, et al.
Published: (2021)

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
by: Baligács, Júlia, et al.
Published: (2024)

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

Top-k Stabbing Interval Queries
by: Akram, Waseem, et al.
Published: (2024)

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
by: Manthey, Bodo, et al.
Published: (2023)

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

Efficient Enumeration of At Most $k$-Out Polygons
by: Akram, Waseem, et al.
Published: (2025)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Approximately: Independence Implies Vertex Cover
by: Har-Peled, Sariel
Published: (2023)

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

Adversarially Robust Approximate Furthest Neighbor
by: Banihashem, Kiarash, et al.
Published: (2026)

On Approximating the Weighted Region Problem in Square Tessellations
by: Kakimura, Naonori, et al.
Published: (2024)

Performance bounds for nearest neighbor search with k-d trees
by: Bazzani, Marco, et al.
Published: (2026)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)