Approximation Schemes for the Restricted Shortest Path Problem
From MaRDI portal
Publication:4016708
DOI10.1287/moor.17.1.36zbMath0763.90083OpenAlexW2130626677WikidataQ110970412 ScholiaQ110970412MaRDI QIDQ4016708
Publication date: 16 January 1993
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.17.1.36
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
Knapsack problem with objective value gaps, Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks, Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context, Complexity results for the linear time-cost tradeoff problem with multiple milestones and completely ordered jobs, Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications, Formal language constrained path problems, DIAMETER-CONSTRAINED STEINER TREES, Approximation schemes for a class of subset selection problems, Single machine scheduling with two competing agents and equal job processing times, Minimum cost paths over dynamic networks, Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms, A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs, Approximating the Restricted 1-Center in Graphs, Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price, A computer-aided process planning model based on genetic algorithms, Simple paths with exact and forbidden lengths, PGAS: privacy-preserving graph encryption for accurate constrained shortest distance queries, An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem, The capacity expansion path problem in networks, On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks, Approximation Methods for Multiobjective Optimization Problems: A Survey, Errata and comments on ``Approximation algorithms for the capacitated plant allocation problem, Multi-postpath-based lookahead multiconstraint QoS routing, The cross-entropy method for solving bi-criteria network flow problems in discrete-time dynamic networks, Unnamed Item, An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem, Compact location problems with budget and communication constraints, New approaches to multi-objective optimization, Trajectory planning for unmanned aerial vehicles: a network optimization approach, Improving the solution complexity of the scheduling problem with deadlines: A general technique, An FPTAS for minimizing the product of two non-negative linear cost functions, The most vital nodes with respect to independent set and vertex cover, 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, Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines, Single-machine scheduling of multiple projects with controllable processing times, Unnamed Item, General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems, Finding cheapest deadline paths, On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow, Approximating some network design problems with node costs, Minimum diameter cost-constrained Steiner trees, The subdivision-constrained routing requests problem, Polynomial time approximation schemes for the constrained minimum spanning tree problem, Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph, Scheduling two projects with controllable processing times in a single-machine environment, 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, A just-in-time scheduling problem with two competing agents, Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, Supply chain scheduling to minimize holding costs with outsourcing, Fast approximation algorithms for routing problems with hop-wise constraints, Approximation scheme for restricted discrete gate sizing targeting delay minimization, Maximum probability shortest path problem, Constrained shortest path with uncertain transit times, The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles, Multi-criteria approximation schemes for the resource constrained shortest path problem, Bi-objective matchings with the triangle inequality, A generalized approximation framework for fractional network flow and packing problems, Two-agent parallel machine scheduling with a restricted number of overlapped reserved tasks, Two-agent single-machine scheduling problem with just-in-time jobs, Approximation algorithms for constructing some required structures in digraphs, A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation, A better approximation algorithm for the budget prize collecting tree problem., Effective Algorithms for a Class of Discrete Valued Optimal Control Problems, Bounded-hops power assignment in ad hoc wireless networks, The constrained minimum weighted sum of job completion times problem, A simple efficient approximation scheme for the restricted shortest path problem, Facility location with dynamic distance functions, Approximation algorithms for multi-agent scheduling to minimize total weighted completion time, Complexity of single machine scheduling subject to nonnegative inventory constraints, Bi-criteria path problem with minimum length and maximum survival probability, Maximum probabilistic all-or-nothing paths, Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph, A new model for path planning with interval data, Bulk-robust combinatorial optimization, Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees, Modifying edges of a network to obtain short subgraphs, A polynomial solvable minimum risk spanning tree problem with interval data, Constrained Steiner trees in Halin graphs, Approximation algorithms for constructing required subgraphs using stock pieces of fixed length, Bicriteria Network Design Problems, Approximating the weight of shallow Steiner trees, Improved approximation algorithms for the combination problem of parallel machine scheduling and path, On Accuracy of Approximation for the Resource Constrained Shortest Path Problem, An improved FPTAS for Restricted Shortest Path., Unnamed Item, Efficiently computing succinct trade-off curves, On budget-constrained flow improvement., Approximation algorithms for multi-parameter graph optimization problems, When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem, A heuristic for cumulative vehicle routing using column generation
