Buchumschlag

Sublinear Algorithms for TSP via Path Covers

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Behnezhad, Soheil, Roghani, Mohammad, Rubinstein, Aviad, Saberi, Amin
Format:	Preprint
Veröffentlicht:	2023
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 Maximum Matching Requires Almost Quadratic Time
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2024)

Sublinear Metric Steiner Forest via Maximal Independent Set
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2025)

Stochastic Matching via In-n-Out Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2025)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Single-Pass Streaming CSPs via Two-Tier Sampling
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)

Lower Bounds for Non-adaptive Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Half-Approximating Maximum Dicut in the Streaming Setting
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

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

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
von: Mao, Xiao, et al.
Veröffentlicht: (2026)

Stable Matching with Interviews
von: Ashlagi, Itai, et al.
Veröffentlicht: (2025)

Correlation Clustering Beyond the Pivot Algorithm
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
von: Rubinstein, Aviad
Veröffentlicht: (2016)

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
von: Rubinstein, Aviad, et al.
Veröffentlicht: (2026)

Markov Chains with Rewinding
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)

Computing String Covers in Sublinear Time
von: Radoszewski, Jakub, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

A Simple Analysis of Ranking in General Graphs
von: Derakhshan, Mahsa, et al.
Veröffentlicht: (2025)

Improved Approximation for Ranking on General Graphs
von: Derakhshan, Mahsa, et al.
Veröffentlicht: (2025)

Simple and Optimal Sublinear Algorithms for Mean Estimation
von: Bertolotti, Beatrice, et al.
Veröffentlicht: (2024)

Stochastic Matching via Local Sparsification
von: Ahmadian, Sara, et al.
Veröffentlicht: (2026)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
von: Hayderi, Alexandre, et al.
Veröffentlicht: (2024)

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

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

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
von: Ferber, Asaf, et al.
Veröffentlicht: (2025)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
von: Peng, Pan, et al.
Veröffentlicht: (2025)

Parallel Sampling via Counting
von: Anari, Nima, et al.
Veröffentlicht: (2024)

Near-Optimal Bayesian Online Assortment of Reusable Resources
von: Feng, Yiding, et al.
Veröffentlicht: (2025)

Optimal Rounding for Two-Stage Bipartite Matching
von: Pollner, Tristan, et al.
Veröffentlicht: (2025)

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)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
von: Braverman, Mark, et al.
Veröffentlicht: (2024)