Buchumschlag

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kisfaludi-Bak, Sándor, Nederlof, Jesper, Węgrzycki, Karol
Format:	Preprint
Veröffentlicht:	2020
Schlagworte:	Computational Geometry Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

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

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

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)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
von: Kluk, Kacper, et al.
Veröffentlicht: (2025)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
von: Björklund, Andreas, et al.
Veröffentlicht: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
von: Blank, Lotte, et al.
Veröffentlicht: (2026)

On connections between k-coloring and Euclidean k-means
von: Aman, Enver, et al.
Veröffentlicht: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Mind the Gap? Not for SVP Hardness under ETH!
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2025)

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

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

Approximate Algorithms for Chamfer Distance Under Translation
von: Halevi, Gil, et al.
Veröffentlicht: (2026)

On Approximating the Dynamic and Discrete Network Flow Problem
von: Manna, Bubai, et al.
Veröffentlicht: (2024)

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

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2026)

Improved Hardness of BDD and SVP Under Gap-(S)ETH
von: Bennett, Huck, et al.
Veröffentlicht: (2021)

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

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

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

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

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

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
von: Grossman, Ofer, et al.
Veröffentlicht: (2023)

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

TSP Escapes the $O(2^n n^2)$ Curse
von: Stoian, Mihail
Veröffentlicht: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
von: Goodrich, Michael T., et al.
Veröffentlicht: (2024)

On Approximability of $\ell_2^2$ Min-Sum Clustering
von: S., Karthik C., et al.
Veröffentlicht: (2024)

Universal Solvability for Robot Motion Planning on Graphs
von: Dhar, Anubhav, et al.
Veröffentlicht: (2025)

Inapproximability of Maximum Diameter Clustering for Few Clusters
von: Fleischmann, Henry, et al.
Veröffentlicht: (2023)

Recognizing 2-Layer and Outer $k$-Planar Graphs
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2024)

Subcoloring of (Unit) Disk Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2025)

Beyond Bits: An Introduction to Computation over the Reals
von: Miltzow, Tillmann
Veröffentlicht: (2026)

Fast and simple multiplication of bounded twin-width matrices
von: Kozma, László, et al.
Veröffentlicht: (2026)