An improved FPTAS for Restricted Shortest Path.
From MaRDI portal
Publication:1853085
DOI10.1016/S0020-0190(02)00205-3zbMath1051.68152OpenAlexW2061701207MaRDI QIDQ1853085
Lisa Zhang, Funda Ergün, Rakesh Kumar Sinha
Publication date: 21 January 2003
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00205-3
Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items
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 ⋮ Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms ⋮ Approximating the Restricted 1-Center in Graphs ⋮ A simulated annealing for multi-criteria network path problems ⋮ Simple paths with exact and forbidden lengths ⋮ The capacity expansion path problem in networks ⋮ 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 ⋮ Improving the solution complexity of the scheduling problem with deadlines: A general technique ⋮ Approximating the restricted 1-center in graphs ⋮ Finding cheapest deadline paths ⋮ The subdivision-constrained routing requests problem ⋮ Polynomial time approximation schemes for the constrained minimum 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 ⋮ Approximation scheme for restricted discrete gate sizing targeting delay minimization ⋮ 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 ⋮ Approximation algorithms for constructing some required structures in digraphs ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ The \(k\)-centrum shortest path problem ⋮ Maximum probabilistic all-or-nothing paths ⋮ One-exact approximate Pareto sets ⋮ Improved approximation algorithms for the combination problem of parallel machine scheduling and path ⋮ Efficiently computing succinct trade-off curves ⋮ When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem
Cites Work
