Image de couverture de livre

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Koh, Zhuan Khye, Weinstein, Omri, Yingchareonthawornchai, Sorrachai
Format:	Preprint
Publié:	2024
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

Hardness Amplification for Dynamic Binary Search Trees
par: Jiang, Shunhua, et autres
Publié: (2024)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
par: Agarwal, Arpit, et autres
Publié: (2024)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
par: Blikstad, Joakim, et autres
Publié: (2025)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
par: Jiang, Yonggang, et autres
Publié: (2025)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
par: Fischer, Olivier, et autres
Publié: (2025)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
par: Jiang, Yonggang, et autres
Publié: (2025)

Online Matching on $3$-Uniform Hypergraphs
par: Borst, Sander, et autres
Publié: (2024)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
par: Koh, Zhuan Khye, et autres
Publié: (2021)

A Little Clairvoyance Is All You Need
par: Gupta, Anupam, et autres
Publié: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
par: Gupta, Anupam, et autres
Publié: (2026)

Improved Sparse Recovery for Approximate Matrix Multiplication
par: Uffenheimer, Yahel, 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)

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

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

(Approximate) Matrix Multiplication via Convolutions
par: Uffenheimer, Yahel, et autres
Publié: (2025)

Polylogarithmic Approximation for Robust s-t Path
par: Li, Shi, et autres
Publié: (2023)

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

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
par: Hua, Kevin, et autres
Publié: (2024)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
par: Driemel, Anne, et autres
Publié: (2026)

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

On the Correlation Gap of Matroids
par: Husić, Edin, et autres
Publié: (2022)

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

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

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
par: Chekuri, Chandra, et autres
Publié: (2024)

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

A Framework for Building Data Structures from Communication Protocols
par: Andoni, Alexandr, et autres
Publié: (2025)

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
par: Xu, Haoran, et autres
Publié: (2026)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
par: Brand, Jan van den, et autres
Publié: (2025)

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)

Approximating Partition in Near-Linear Time
par: Chen, Lin, et autres
Publié: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
par: Anand, Aditya, et autres
Publié: (2025)

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
par: Christalla, Manuel, et autres
Publié: (2025)

Memory Reallocation with Polylogarithmic Overhead
par: Jin, Ce
Publié: (2026)

Discrepancy Minimization in Input-Sparsity Time
par: Deng, Yichuan, et autres
Publié: (2022)

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

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

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

Dynamic Longest Common Substring in Polylogarithmic Time
par: Charalampopoulos, Panagiotis, et autres
Publié: (2020)

On Thin Perfect Matchings up to Polylogarithmic Factors
par: Haqi, Alireza, et autres
Publié: (2026)