Cover Image

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mömke, Tobias, Zhou, Hang
Format:	Preprint
Published:	2024
Subjects:	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)

Approximating Prize-Collecting Variants of TSP
by: Alimi, Morteza, et al.
Published: (2024)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
by: Alipour, Sharareh, et al.
Published: (2025)

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

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
by: Friggstad, Zachary, et al.
Published: (2025)

Approximating Traveling Salesman Problems Using a Bridge Lemma
by: Böhm, Martin, et al.
Published: (2024)

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

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

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
by: Christalla, Manuel, et al.
Published: (2025)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
by: Rohwedder, Lars
Published: (2025)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
by: Saller, Sophia, et al.
Published: (2023)

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
by: Jansen, Bart M. P., et al.
Published: (2025)

4/3-Approximation of Graphic TSP
by: Çivril, Ali
Published: (2023)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
by: Bringmann, Karl, et al.
Published: (2026)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

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

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

Improved FPT Approximation for Non-metric TSP
by: Bampis, Evripidis, et al.
Published: (2024)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
by: Mömke, Tobias, et al.
Published: (2024)

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
by: Alimi, Morteza, et al.
Published: (2025)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
by: Zhao, Jingyang, et al.
Published: (2025)

A Better-Than-1.6-Approximation for Prize-Collecting TSP
by: Blauth, Jannis, et al.
Published: (2023)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
by: Armbruster, Susanne, et al.
Published: (2024)

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
by: Stoian, Mihail
Published: (2026)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Mind the Gap? Not for SVP Hardness under ETH!
by: Aggarwal, Divesh, et al.
Published: (2025)

Online Metric TSP
by: Bertram, Christian
Published: (2025)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
by: Foucaud, Florent, et al.
Published: (2025)

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

Approximating Partition in Near-Linear Time
by: Chen, Lin, et al.
Published: (2024)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
by: Mao, Xiao, et al.
Published: (2026)

Tight Analyses of Ordered and Unordered Linear Probing
by: Braverman, Mark, et al.
Published: (2025)

Approximating Directed Connectivity in Almost-Linear Time
by: Quanrud, Kent
Published: (2025)

Improved Hardness of BDD and SVP Under Gap-(S)ETH
by: Bennett, Huck, et al.
Published: (2021)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)