Copertina

Waiting is not easy but worth it: the online TSP on the line revisited

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chen, Pei-Chuan, Demaine, Erik D., Liao, Chung-Shou, Wei, Hao-Ting
Natura:	Preprint
Pubblicazione:	2019
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Waiting is worth it and can be improved with predictions
di: Liang, Ya-Chun, et al.
Pubblicazione: (2025)

Online Metric TSP
di: Bertram, Christian
Pubblicazione: (2025)

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

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

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

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

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

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

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

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

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

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

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
di: Kalavas, Andreas, et al.
Pubblicazione: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
di: Kalavas, Andreas, et al.
Pubblicazione: (2025)

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

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

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

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

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

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

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

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

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

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

Algorithmic strategies for finding the best TSP 2-OPT move in average sub-quadratic time
di: Lancia, Giuseppe, et al.
Pubblicazione: (2024)

Graph Threading
di: Demaine, Erik D., et al.
Pubblicazione: (2023)

Lower bounds for the universal TSP on the plane
di: Kravaris, Cosmas
Pubblicazione: (2024)

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

Speed-robust scheduling revisited
di: Minařík, Josef, et al.
Pubblicazione: (2024)

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

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

Practical colinear chaining on sequences revisited
di: Rizzo, Nicola, et al.
Pubblicazione: (2025)

SYK thermal expectations are classically easy at any temperature
di: Zlokapa, Alexander, et al.
Pubblicazione: (2026)

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

TSP Escapes the $O(2^n n^2)$ Curse
di: Stoian, Mihail
Pubblicazione: (2024)

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

Graph Threading with Turn Costs
di: Demaine, Erik D., et al.
Pubblicazione: (2024)

Dynamic online matching with budget refills
di: Cherifa, Maria, et al.
Pubblicazione: (2024)

Improved online load balancing with known makespan
di: Böhm, Martin, et al.
Pubblicazione: (2024)

Counting Locally Optimal Tours in the TSP
di: Manthey, Bodo, et al.
Pubblicazione: (2024)