2017/11/01 by David Holzmüller, Holzmüller, David · 1 citation
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #cs.CC #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1711.00284
Incorporated more review suggestions
arxiv created 2019/11/02 · arxiv updated 2019/11/05
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 ∈ Ω(n log n), we obtain (1 + ε)-approximations in time O(mn/ε). 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.