Copertina

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Gaudio, Julia, Guan, Charlie K.
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Geometry Data Structures and Algorithms Combinatorics Probability
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

The Squishy Grid Problem
di: Cai, Zixi, et al.
Pubblicazione: (2025)

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

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

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

Improved Upper Bounds for the Directed Flow-Cut Gap
di: Bodwin, Greg, et al.
Pubblicazione: (2026)

Balanced TSP partitioning
di: Berendsohn, Benjamin Aram, et al.
Pubblicazione: (2025)

Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching
di: Hougardy, Stefan, et al.
Pubblicazione: (2024)

Improved space-time tradeoff for TSP via extremal set systems
di: Dallant, Justin, et al.
Pubblicazione: (2026)

Sampling from convex sets with a cold start using multiscale decompositions
di: Narayanan, Hariharan, et al.
Pubblicazione: (2022)

Reconstructing Riemannian Metrics From Random Geometric Graphs
di: Huang, Han, et al.
Pubblicazione: (2025)

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

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
di: Filtser, Arnold
Pubblicazione: (2024)

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth
di: Cabello, Sergio, et al.
Pubblicazione: (2025)

On Computing Vertex Connectivity of 1-Plane Graphs
di: Biedl, Therese, et al.
Pubblicazione: (2022)

Zone Theorem for Arrangements in three dimensions
di: Saxena, Sanjeev
Pubblicazione: (2020)

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

Analysis of a Random Local Search Algorithm for Dominating Set
di: Higl, Hendrik
Pubblicazione: (2026)

Burning rooted graph products
di: Peca-Medlin, John
Pubblicazione: (2026)

Heights of butterfly trees
di: Peca-Medlin, John, et al.
Pubblicazione: (2025)

Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz--Parisi Potential
di: Koehler, Frederic, et al.
Pubblicazione: (2025)

Mixing on Generalized Associahedra
di: Chang, William, et al.
Pubblicazione: (2024)

Zero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region
di: Shao, Shuai, et al.
Pubblicazione: (2025)

Fast Mixing in Sparse Random Ising Models
di: Liu, Kuikui, et al.
Pubblicazione: (2024)

Minimal spanning arborescence
di: Ray, Gourab, et al.
Pubblicazione: (2024)

The Horton-Strahler number of butterfly trees
di: Peca-Medlin, John
Pubblicazione: (2025)

An Easy Proof of a Weak Version of Chernoff inequality
di: Har-Peled, Sariel
Pubblicazione: (2025)

Polynomial-time sampling despite disorder chaos
di: Ma, Eric, et al.
Pubblicazione: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Some easy optimization problems have the overlap-gap property
di: Li, Shuangping, et al.
Pubblicazione: (2024)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
di: Bansal, Nikhil, et al.
Pubblicazione: (2025)

Better approximation guarantee for Asymmetric TSP
di: Vygen, Jens
Pubblicazione: (2026)

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

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

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

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

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
di: Casteigts, Arnaud, et al.
Pubblicazione: (2020)

Space Complexity of Euclidean Clustering
di: Zhu, Xiaoyi, et al.
Pubblicazione: (2024)

Bounding Width on Graph Classes of Constant Diameter
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2025)

Solving a Random Asymmetric TSP Exactly in Quasi-Polynomial Time w.h.p
di: Bell, Tolson, et al.
Pubblicazione: (2023)