# A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs

Preprint · Vikrant Ashvinkumar

- Archive id: arxiv:2610.18337
- Published: 2026-10-13
- arXiv: https://arxiv.org/abs/2610.18337
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.18337
- PDF: https://arxiv.org/pdf/2610.18337
- Provenance: arxiv

## 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$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.