# Improved Approximation Schemes for the Restricted Shortest Path Problem

Preprint · David Holzmüller

- Archive id: arxiv:1711.00284
- Published: 2017-11-01
- arXiv: https://arxiv.org/abs/1711.00284
- Source URL: https://arxiv.org/abs/1711.00284
- PDF: https://arxiv.org/pdf/1711.00284
- Provenance: arxiv

## Abstract

The Restricted Shortest Path (RSP) problem, also known as the Delay-Constrained Least-Cost (DCLC) problem, is an NP-hard bicriteria optimization problem on graphs with $n$ vertices and $m$ edges. In a graph where each edge is assigned a cost and a delay, the goal is to find a min-cost path which does not exceed a delay bound. In this paper, we present improved approximation schemes for RSP on several graph classes. For planar graphs, undirected graphs with positive integer resource (= delay) values, and graphs with $m \\in Ω(n \\log n)$, we obtain $(1 + \\varepsilon)$-approximations in time $O(mn/\\varepsilon)$. For general graphs and directed acyclic graphs, we match the results by Xue et al. (2008, \[10\]) and Ergun et al. (2002, \[1\]), respectively, but with arguably simpler algorithms.

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

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