arXiv preprint ·
A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In the restricted shortest paths problem, we are given an $n$-vertex $m$-edge directed graph $G$ whose edges are assigned two non-negative weights (or resources) called lengths and costs, a source vertex $s$, and a cost threshold $C$. The goal is to find, for each target vertex $t$, the length of the shortest $(s,t)$-path whose total cost is at most $C$. Ashvinkumar, Bernstein, and Karczmarz (SODA 2025) gave the first randomized bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm on directed graphs running in sub-$mn$ time, answering a problem posed by Bernstein (SODA 2012). We substantially improve this on two fronts, supplying a deterministic bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm running in near-linear time. Our approach straightforwardly generalizes to more than two resources. For $k$ resources, a deterministic $(1+\varepsilon_1,\ldots,1+\varepsilon_k)$-approximate algorithm running in near-linear time is possible, with $\varepsilon_1=\ldots=\varepsilon_k=\varepsilon$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Improved Combinatorial Auctions with and without Samples
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage
Query Complexity of Densest Sub(hyper)graph Problems
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.