Cover Image

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Makarychev, Yury, Ovsiankin, Max, Tani, Erasmo
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Approximability of Steiner Tree in $\ell_p$-metrics
by: Fleischmann, Henry, et al.
Published: (2023)

Dynamic Metric Embedding into $\ell_p$ Space
by: Banihashem, Kiarash, et al.
Published: (2024)

Coresets for Multiple $\ell_p$ Regression
by: Woodruff, David P., et al.
Published: (2024)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
by: Woodruff, David P., et al.
Published: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
by: Woodruff, David P., et al.
Published: (2023)

Turnstile $\ell_p$ leverage score sampling with applications
by: Munteanu, Alexander, et al.
Published: (2024)

Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$
by: Chiclana, Rafael, et al.
Published: (2025)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
by: Munteanu, Alexander, et al.
Published: (2024)

The Power of Recursive Embeddings for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2025)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2026)

Iterative Refinement for $\ell_p$-norm Regression
by: Adil, Deeksha, et al.
Published: (2019)

The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
by: Li, Yi, et al.
Published: (2022)

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
by: Davies, Sami, et al.
Published: (2025)

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
by: Makarychev, Yury
Published: (2026)

The Steiner Shortest Path Tree Problem
by: Asher, Omer, et al.
Published: (2025)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

Constraint Satisfaction Problems with Advice
by: Ghoshal, Suprovat, et al.
Published: (2024)

The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms
by: Manoj, Naren Sarayu, et al.
Published: (2023)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Query-decision Regression between Shortest Path and Minimum Steiner Tree
by: Tong, Guangmo, et al.
Published: (2024)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Approximation Algorithms for Steiner Connectivity Augmentation
by: Hathcock, Daniel, et al.
Published: (2023)

Faster Approximate Fixed Points of $\ell_\infty$-Contractions
by: Feodorov, Andrei, et al.
Published: (2026)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
by: Madani, Amirali, et al.
Published: (2025)

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Improved 2-Approximate Shortest Paths for close vertex pairs
by: Gupta, Manoj
Published: (2025)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
by: Kumar, Mithilesh, et al.
Published: (2016)

Massively Parallel Algorithms for Approximate Shortest Paths
by: Dory, Michal, et al.
Published: (2024)

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
by: Fischer, Nick, et al.
Published: (2025)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
by: Choudhary, Keerti, et al.
Published: (2025)

Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
by: Bairaktari, Konstantina, et al.
Published: (2025)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)