Imagen de Portada

Hardness of Approximation for Shortest Path with Vector Costs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Carlson, Charlie, Makarychev, Yury, Mosenzon, Ron
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
por: Makarychev, Yury, et al.
Publicado: (2024)

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
por: Makarychev, Yury
Publicado: (2026)

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
por: Mosenzon, Ron
Publicado: (2025)

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

Constraint Satisfaction Problems with Advice
por: Ghoshal, Suprovat, et al.
Publicado: (2024)

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

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

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

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

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

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

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

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

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
por: Yamano, Ryosuke, et al.
Publicado: (2026)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
por: Chuzhoy, Julia, et al.
Publicado: (2025)

The Discrepancy of Shortest Paths
por: Bodwin, Greg, et al.
Publicado: (2024)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
por: Yan, Shuyi
Publicado: (2025)

Scalable Algorithms for Individual Preference Stable Clustering
por: Mosenzon, Ron, et al.
Publicado: (2024)

Shortest Paths in Multimode Graphs
por: Kirkpatrick, Yael, et al.
Publicado: (2025)

On Constrained and k Shortest Paths
por: Bendahi, Abderrahim, et al.
Publicado: (2024)

All-Hops Shortest Paths
por: Williams, Virginia Vassilevska, et al.
Publicado: (2024)

Incremental Approximate Single-Source Shortest Paths with Predictions
por: McCauley, Samuel, et al.
Publicado: (2025)

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

Hierarchical Multicriteria Shortest Path Search
por: Kurbanov, Temirlan, et al.
Publicado: (2025)

Shortcutting for Negative-Weight Shortest Path
por: Li, George Z., et al.
Publicado: (2025)

Verifying Shortest Paths in Linear Time
por: Shokry, Ahmed, et al.
Publicado: (2024)

Fully Dynamic Shortest Paths in Sparse Digraphs
por: Karczmarz, Adam, et al.
Publicado: (2024)

Parameterized Complexity of Finding Dissimilar Shortest Paths
por: Funayama, Ryo, et al.
Publicado: (2024)

Breaking the Bellman-Ford Shortest-Path Bound
por: Elmasry, Amr
Publicado: (2024)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
por: Li, Jason
Publicado: (2025)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
por: Pilipczuk, Michał, et al.
Publicado: (2025)

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

Knapsack: Connectedness, Path, and Shortest-Path
por: Dey, Palash, et al.
Publicado: (2023)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
por: Dalirrooyfard, Mina, et al.
Publicado: (2025)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
por: Dalirrooyfard, Mina, et al.
Publicado: (2026)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
por: Dalirrooyfard, Mina, et al.
Publicado: (2024)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
por: Haeupler, Bernhard, et al.
Publicado: (2025)

All-Pairs Shortest Paths with Few Weights per Node
por: Abboud, Amir, et al.
Publicado: (2025)

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

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
por: Geis, Lukas, et al.
Publicado: (2024)