A simple efficient approximation scheme for the restricted shortest path problem

DOI10.1016/S0167-6377(01)00069-4MaRDI QIDQ5945392zbMATH OpenOpenAlexFDO

Authors Dean H. Lorenz, Danny Raz

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

zbMATH Keywords

polynomial approximation schemeshortest path problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Approximation Schemes for the Restricted Shortest Path Problem
• An improved FPTAS for Restricted Shortest Path.
• Near linear time \((1 + \epsilon)\)-approximation for restricted shortest paths in undirected graphs
• -approximation schemes for the constrained shortest path problem
• Multi-criteria approximation schemes for the resource constrained shortest path problem

Cites work

• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Errata and comments on ``Approximation algorithms for the capacitated plant allocation problem
• The network inhibition problem

Cited in

(55)

• A PTAS for weight constrained Steiner trees in series--parallel graphs.
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem
• 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
• A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation
• An improved FPTAS for Restricted Shortest Path.
• Trajectory planning for unmanned aerial vehicles: a network optimization approach
• One-exact approximate Pareto sets
• Mobile facility location: combinatorial filtering via weighted occupancy
• Bi-criteria path problem with minimum length and maximum survival probability
• Maximum probabilistic all-or-nothing paths
• Improved approximation algorithms for computing k disjoint paths subject to two constraints
• Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context
• Approximation schemes for a class of subset selection problems
• A general approximation method for bicriteria minimization problems
• On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks
• Approximating the restricted 1-center in graphs
• Approximation algorithms and hardness results for labeled connectivity problems
• When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem
• Efficiently computing succinct trade-off curves
• Finding cheapest deadline paths
• Approximating corridors and tours via restriction and relaxation techniques
• The cross-entropy method for solving bi-criteria network flow problems in discrete-time dynamic networks
• Single machine scheduling with two competing agents and equal job processing times
• Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
• Approximating the Restricted 1-Center in Graphs
• Effective algorithms for a class of discrete valued optimal control problems
• scientific article; zbMATH DE number 4035602 (Why is no real title available?)
• An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem
• A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem
• Approximation Schemes for the Restricted Shortest Path Problem
• New approaches to multi-objective optimization
• Improved approximation algorithms for directed Steiner forest
• Polynomial time approximation schemes for the constrained minimum spanning tree problem
• Constrained Steiner trees in Halin graphs
• Simple paths with exact and forbidden lengths
• -approximation schemes for the constrained shortest path problem
• Fast approximation algorithms for routing problems with hop-wise constraints
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms
• Near linear time \((1 + \epsilon)\)-approximation for restricted shortest paths in undirected graphs
• On Accuracy of Approximation for the Resource Constrained Shortest Path Problem
• An exact bidirectional pulse algorithm for the constrained shortest path
• Online learning for route planning with on-time arrival reliability
• A note on approximating the min-max vertex disjoint paths on directed acyclic graphs
• Approximating the shortest path problem with scenarios
• Simple approximations for general spanner problems
• A generalized combination of parallel machine scheduling and path
• Approximation algorithms for directed weighted spanners
• Approximate multi-objective search
• Directed buy-at-bulk spanners
• Approximation algorithms for optimal hopsets
• Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications

This page was built for publication: A simple efficient approximation scheme for the restricted shortest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5945392)