Image de couverture de livre

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Christalla, Manuel, Puhlmann, Luise, Traub, Vera
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Steiner Forest: A Simplified Better-Than-2 Approximation
par: Gupta, Anupam, et autres
Publié: (2025)

The Bidirected Cut Relaxation for Steiner Tree: Better Integrality Gap Bounds and the Limits of Moat Growing
par: Paschmanns, Paul, et autres
Publié: (2026)

Approximation Schemes for Planar Graph Connectivity Problems
par: Neuwohner, Meike, et autres
Publié: (2025)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
par: Mömke, Tobias, et autres
Publié: (2024)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
par: Byrka, Jarosław, et autres
Publié: (2024)

Approximating Prize-Collecting Variants of TSP
par: Alimi, Morteza, et autres
Publié: (2024)

4/3-Approximation of Graphic TSP
par: Çivril, Ali
Publié: (2023)

Better approximation guarantee for Asymmetric TSP
par: Vygen, Jens
Publié: (2026)

Improved FPT Approximation for Non-metric TSP
par: Bampis, Evripidis, et autres
Publié: (2024)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
par: Zhao, Jingyang, et autres
Publié: (2025)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
par: Ren, Kinter, et autres
Publié: (2024)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
par: Alipour, Sharareh, et autres
Publié: (2025)

A Better-Than-1.6-Approximation for Prize-Collecting TSP
par: Blauth, Jannis, et autres
Publié: (2023)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
par: Kisfaludi-Bak, Sándor, et autres
Publié: (2020)

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
par: Baligács, Júlia, et autres
Publié: (2024)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
par: Armbruster, Susanne, et autres
Publié: (2024)

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

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
par: Barak, Zohar, et autres
Publié: (2026)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
par: Koh, Zhuan Khye, et autres
Publié: (2024)

Faster Approximation Scheme for Euclidean $k$-TSP
par: van Wijland, Ernest, et autres
Publié: (2023)

Online Metric TSP
par: Bertram, Christian
Publié: (2025)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
par: Saller, Sophia, et autres
Publié: (2023)

On the Bidirected Cut Relaxation for Steiner Forest
par: Byrka, Jarosław, et autres
Publié: (2024)

Solving a Random Asymmetric TSP Exactly in Quasi-Polynomial Time w.h.p
par: Bell, Tolson, et autres
Publié: (2023)

Dual Charging for Half-Integral TSP
par: Klein, Nathan, et autres
Publié: (2025)

Sublinear Algorithms for TSP via Path Covers
par: Behnezhad, Soheil, et autres
Publié: (2023)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
par: Kisfaludi-Bak, Sándor, et autres
Publié: (2026)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
par: Kalavas, Andreas, et autres
Publié: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
par: Kalavas, Andreas, et autres
Publié: (2025)

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks
par: Blauth, Jannis, et autres
Publié: (2022)

Matroid-Based TSP Rounding for Half-Integral Solutions
par: Gupta, Anupam, et autres
Publié: (2021)

Waiting is not easy but worth it: the online TSP on the line revisited
par: Chen, Pei-Chuan, et autres
Publié: (2019)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
par: Swamy, Chaitanya, et autres
Publié: (2025)

A Lower Bound for the Max Entropy Algorithm for TSP
par: Jin, Billy, et autres
Publié: (2023)

Balanced TSP partitioning
par: Berendsohn, Benjamin Aram, et autres
Publié: (2025)

Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms
par: Housni, Omar El, et autres
Publié: (2024)

Adaptivity Gaps for Stochastic Probing with Subadditive Functions
par: Li, Jian, et autres
Publié: (2025)

Algorithmic strategies for finding the best TSP 2-OPT move in average sub-quadratic time
par: Lancia, Giuseppe, et autres
Publié: (2024)

Lower bounds for the universal TSP on the plane
par: Kravaris, Cosmas
Publié: (2024)

Improved space-time tradeoff for TSP via extremal set systems
par: Dallant, Justin, et autres
Publié: (2026)