Imagen de Portada

Lower bounds for the universal TSP on the plane

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Kravaris, Cosmas
Formato:	Preprint
Publicado:	2024
Materias:	Metric Geometry Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
por: Bai, Xingjian, et al.
Publicado: (2024)

Nearly-Tight Bounds for Zonotope Containment and Beyond
por: Eisenbrand, Friedrich, et al.
Publicado: (2026)

The Power of Recursive Embeddings for $\ell_p$ Metrics
por: Krauthgamer, Robert, et al.
Publicado: (2025)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
por: Krauthgamer, Robert, et al.
Publicado: (2026)

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

Fitting trees to $\ell_1$-hyperbolic distances
por: Yim, Joon-Hyeok, et al.
Publicado: (2024)

Random zero sets with local growth guarantees
por: Chang, Alan, et al.
Publicado: (2024)

Time warping with Hellinger elasticity
por: Billig, Yuly
Publicado: (2026)

Time complexity of the Analyst's Traveling Salesman algorithm
por: Ramirez, Anthony, et al.
Publicado: (2022)

$L_1$ and $L_2$ embeddings of the symmetric group
por: Kravaris, Cosmas
Publicado: (2025)

O(1)-Distortion Planar Emulators for String Graphs
por: Chang, Hsien-Chih, et al.
Publicado: (2025)

Balanced TSP partitioning
por: Berendsohn, Benjamin Aram, et al.
Publicado: (2025)

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

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

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

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

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

An Optimal Algorithm for Half-plane Hitting Set
por: Liu, Gang, et al.
Publicado: (2025)

Parameterized and approximation algorithms for coverings points with segments in the plane
por: Kowalska, Katarzyna, et al.
Publicado: (2024)

A Lower Bound for the Max Entropy Algorithm for TSP
por: Jin, Billy, et al.
Publicado: (2023)

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

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

Online Metric TSP
por: Bertram, Christian
Publicado: (2025)

On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Subsets of $\mathbb{R}^N$
por: Chiclana, Rafael, et al.
Publicado: (2024)

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

Dual Charging for Half-Integral TSP
por: Klein, Nathan, et al.
Publicado: (2025)

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

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

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

Sublinear Algorithms for TSP via Path Covers
por: Behnezhad, Soheil, et al.
Publicado: (2023)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
por: Khanna, Sanjeev, et al.
Publicado: (2025)

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

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

Matroid-Based TSP Rounding for Half-Integral Solutions
por: Gupta, Anupam, et al.
Publicado: (2021)

Waiting is not easy but worth it: the online TSP on the line revisited
por: Chen, Pei-Chuan, et al.
Publicado: (2019)

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

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

Metric embeddings of cubes into dense subsets of cubes
por: Karamanlis, Miltiadis, et al.
Publicado: (2026)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
por: Gutekunst, Samuel C.
Publicado: (2025)

Fast and simple multiplication of bounded twin-width matrices
por: Kozma, László, et al.
Publicado: (2026)