A simple efficient approximation scheme for the restricted shortest path problem
From MaRDI portal
Publication:5945392
DOI10.1016/S0167-6377(01)00069-4zbMath0992.90057OpenAlexW2074117023MaRDI QIDQ5945392
Publication date: 10 October 2001
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0167-6377(01)00069-4
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (39)
Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context ⋮ Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications ⋮ Approximation schemes for a class of subset selection problems ⋮ Single machine scheduling with two competing agents and equal job processing times ⋮ Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths ⋮ Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms ⋮ Approximating the Restricted 1-Center in Graphs ⋮ Simple paths with exact and forbidden lengths ⋮ An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem ⋮ A general approximation method for bicriteria minimization problems ⋮ On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ The cross-entropy method for solving bi-criteria network flow problems in discrete-time dynamic networks ⋮ An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem ⋮ New approaches to multi-objective optimization ⋮ Trajectory planning for unmanned aerial vehicles: a network optimization approach ⋮ Approximating the restricted 1-center in graphs ⋮ A PTAS for weight constrained Steiner trees in series--parallel graphs. ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ Finding cheapest deadline paths ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Polynomial time approximation schemes for the constrained minimum spanning tree problem ⋮ A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. ⋮ A note on approximating the min-max vertex disjoint paths on directed acyclic graphs ⋮ Fast approximation algorithms for routing problems with hop-wise constraints ⋮ Multi-criteria approximation schemes for the resource constrained shortest path problem ⋮ Discrete representation of the non-dominated set for multi-objective optimization problems using kernels ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation ⋮ Effective Algorithms for a Class of Discrete Valued Optimal Control Problems ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ Maximum probabilistic all-or-nothing paths ⋮ One-exact approximate Pareto sets ⋮ Constrained Steiner trees in Halin graphs ⋮ Unnamed Item ⋮ Efficiently computing succinct trade-off curves ⋮ When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem ⋮ Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints
Cites Work
This page was built for publication: A simple efficient approximation scheme for the restricted shortest path problem
