Image de couverture de livre

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Kyng, Rasmus, Gutenberg, Maximilian Probst, Rieder, Tim
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

Optimal Electrical Oblivious Routing on Expanders
par: Florescu, Cella, et autres
Publié: (2024)

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
par: Gutenberg, Maximilian Probst, et autres
Publié: (2025)

Deterministic Almost-Linear-Time Gomory-Hu Trees
par: Abboud, Amir, et autres
Publié: (2025)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
par: Gutenberg, Maximilian Probst, et autres
Publié: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
par: Meierhans, Simon, et autres
Publié: (2025)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
par: Brand, Jan van den, et autres
Publié: (2024)

An Approximation Algorithm for Graph Label Selection
par: John, Josia, et autres
Publié: (2026)

Near-Optimal Algorithm for Directed Expander Decompositions
par: Sulser, Aurelio L., et autres
Publié: (2024)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
par: Meierhans, Simon, et autres
Publié: (2025)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
par: Das, Debarati, et autres
Publié: (2026)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
par: Chen, Daoyuan, et autres
Publié: (2024)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
par: Ashvinkumar, Vikrant, et autres
Publié: (2026)

Acceleration for Distributed Transshipment and Parallel Maximum Flow
par: Grunau, Christoph, et autres
Publié: (2025)

A Simple Dynamic Spanner via APSP
par: Kyng, Rasmus, et autres
Publié: (2024)

Bootstrapping Dynamic APSP via Sparsification
par: Kyng, Rasmus, et autres
Publié: (2024)

Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression
par: Adil, Deeksha, et autres
Publié: (2024)

Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
par: Chekuri, Chandra, et autres
Publié: (2024)

Tight Sampling Bounds for Eigenvalue Approximation
par: Swartworth, William, et autres
Publié: (2024)

Reviving Thorup's Shortcut Conjecture
par: Bernstein, Aaron, et autres
Publié: (2025)

Hardness and Tight Approximations of Demand Strip Packing
par: Jansen, Klaus, et autres
Publié: (2024)

Deterministic Cache-Oblivious Funnelselect
par: Brodal, Gerth Stølting, et autres
Publié: (2024)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
par: Das, Rathish, et autres
Publié: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
par: Dai, Han, et autres
Publié: (2025)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
par: Chen, Lin, et autres
Publié: (2026)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
par: Bentert, Matthias, et autres
Publié: (2024)

Optimal Non-Oblivious Open Addressing
par: Bender, Michael A., et autres
Publié: (2025)

First Order Stochastic Optimization with Oblivious Noise
par: Diakonikolas, Ilias, et autres
Publié: (2024)

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

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
par: Eberle, Franziska, et autres
Publié: (2024)

Iterative Refinement for $\ell_p$-norm Regression
par: Adil, Deeksha, et autres
Publié: (2019)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
par: Bathie, Gabriel, et autres
Publié: (2025)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
par: Zhao, Jingyang, et autres
Publié: (2025)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
par: Zhao, Jingyang, et autres
Publié: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
par: Zhao, Jingyang, et autres
Publié: (2026)

Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
par: Zhao, Jingyang, et autres
Publié: (2023)

Cache-Oblivious Representation of B-Tree Structures
par: Ondráček, Lukáš, et autres
Publié: (2022)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
par: Pham, Ninh, et autres
Publié: (2025)

Approximating $δ$-Covering
par: Hartmann, Tim A., et autres
Publié: (2024)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
par: Bernstein, Aaron, et autres
Publié: (2025)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
par: Hwang, Samuel, et autres
Publié: (2024)