Buchumschlag

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Alipour, Sharareh, Farokhnejad, Ermiya, Mömke, Tobias
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	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

Approximating Prize-Collecting Variants of TSP
von: Alimi, Morteza, et al.
Veröffentlicht: (2024)

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

Sublinear Algorithms for TSP via Path Covers
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2023)

Deterministic $k$-Median Clustering in Near-Optimal Time
von: Costa, Martín, et al.
Veröffentlicht: (2025)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2026)

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
von: Alimi, Morteza, et al.
Veröffentlicht: (2025)

Robust Multiagent Collaboration Through Weighted Max-Min T-Joins
von: Alipour, Sharareh
Veröffentlicht: (2026)

Improved FPT Approximation for Non-metric TSP
von: Bampis, Evripidis, et al.
Veröffentlicht: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

A Lower Bound for the Max Entropy Algorithm for TSP
von: Jin, Billy, et al.
Veröffentlicht: (2023)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

4/3-Approximation of Graphic TSP
von: Çivril, Ali
Veröffentlicht: (2023)

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

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
von: Ren, Kinter, et al.
Veröffentlicht: (2024)

Online Metric TSP
von: Bertram, Christian
Veröffentlicht: (2025)

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
von: Friggstad, Zachary, et al.
Veröffentlicht: (2025)

A Better-Than-1.6-Approximation for Prize-Collecting TSP
von: Blauth, Jannis, et al.
Veröffentlicht: (2023)

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
von: Christalla, Manuel, et al.
Veröffentlicht: (2025)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

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

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
von: Kalavas, Andreas, et al.
Veröffentlicht: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
von: Kalavas, Andreas, et al.
Veröffentlicht: (2025)

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
von: Stoian, Mihail
Veröffentlicht: (2026)

Approximating Traveling Salesman Problems Using a Bridge Lemma
von: Böhm, Martin, et al.
Veröffentlicht: (2024)

Dual Charging for Half-Integral TSP
von: Klein, Nathan, et al.
Veröffentlicht: (2025)

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

Balanced TSP partitioning
von: Berendsohn, Benjamin Aram, et al.
Veröffentlicht: (2025)

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

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

Better approximation guarantee for Asymmetric TSP
von: Vygen, Jens
Veröffentlicht: (2026)

Matroid-Based TSP Rounding for Half-Integral Solutions
von: Gupta, Anupam, et al.
Veröffentlicht: (2021)

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

Improved space-time tradeoff for TSP via extremal set systems
von: Dallant, Justin, et al.
Veröffentlicht: (2026)

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

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

Fully Dynamic Euclidean k-Means
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2025)

Lower bounds for the universal TSP on the plane
von: Kravaris, Cosmas
Veröffentlicht: (2024)

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
von: Gaudio, Julia, et al.
Veröffentlicht: (2026)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2020)

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