Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
From MaRDI portal
Publication:3762099
DOI10.1287/opre.35.1.70zbMath0623.90084OpenAlexW2066047491MaRDI QIDQ3762099
Publication date: 1987
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.35.1.70
fully polynomial approximation schemesmulti-objective, shortest-path problemsset of Pareto optimal paths
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Sensitivity, stability, parametric optimization (90C31)
Related Items
Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach ⋮ The median tour and maximal covering tour problems: Formulations and heuristics ⋮ Multiobjective transportation network design and routing problems: Taxonomy and annotation ⋮ Multiobjective routing of hazardous materials in stochastic networks ⋮ Decision-making based on approximate and smoothed Pareto curves ⋮ Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications ⋮ On the cardinality of the Pareto set in bicriteria shortest path problems ⋮ A discussion of scalarization techniques for multiple objective integer programming ⋮ Approximation schemes for a class of subset selection problems ⋮ Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications ⋮ Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms ⋮ Approximation schemes for bi-objective combinatorial optimization and their application to the TSP with profits ⋮ Discrete dynamic programming with outcomes in random variable structures ⋮ Approximating the Restricted 1-Center in Graphs ⋮ Simple paths with exact and forbidden lengths ⋮ Vehicle routing problems with alternative paths: an application to on-demand transportation ⋮ On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ Multiobjective routing problems ⋮ Two-phase algorithm for solving the preference-based multicriteria optimal path problem with reference points ⋮ The cross-entropy method for solving bi-criteria network flow problems in discrete-time dynamic networks ⋮ Minmax combinatorial optimization ⋮ Unnamed Item ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ Compact location problems with budget and communication constraints ⋮ New approaches to multi-objective optimization ⋮ Improving the solution complexity of the scheduling problem with deadlines: A general technique ⋮ Simple and efficient bi-objective search algorithms via fast dominance checks ⋮ Approximating the restricted 1-center in graphs ⋮ The interactive analysis of the multicriteria shortest path problem by the reference point method. ⋮ General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems ⋮ Competitive algorithms for the bicriteria \(k\)-server problem ⋮ Finding cheapest deadline paths ⋮ The subdivision-constrained routing requests problem ⋮ An interactive approach to identify the best compromise solution for two objective shortest path problems ⋮ Norm-based approximation in multicriteria programming. ⋮ A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. ⋮ Fuzzy shortest path problems incorporating interactivity among paths. ⋮ Optimal paths in bi-attribute networks with fractional cost functions ⋮ Maximum probability shortest path problem ⋮ Finding representative systems for discrete bicriterion optimization problems ⋮ A survey of recent developments in multiobjective optimization ⋮ On local optima in multiobjective combinatorial optimization problems ⋮ Covers and approximations in multiobjective optimization ⋮ Optimal pricing and composition of multiple bundles: a two-step approach ⋮ Routing with nonlinear multiattribute cost functions ⋮ Reference points and approximation algorithms in multicriteria discrete optimization ⋮ Efficient solutions for the bicriteria network flow problem ⋮ Multiple criteria dynamic programming and multiple knapsack problem ⋮ Approximation algorithms for constructing some required structures in digraphs ⋮ Bicriteria network flow problems: Integer case ⋮ A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems ⋮ Dynamic programming approaches to solve the shortest path problem with forbidden paths ⋮ The quickest path problem with interval lead times ⋮ Approximative solution methods for multiobjective combinatorial optimization. With discussion and a rejoinder by the authors. ⋮ A two-criterion lexicographic algorithm for finding all shortest paths in networks ⋮ Nodal aggregation of resource constraints in a shortest path problem ⋮ Multicriteria adaptive paths in stochastic, time-varying networks ⋮ On finding dissimilar Pareto-optimal paths ⋮ Bounded-hops power assignment in ad hoc wireless networks ⋮ A simple efficient approximation scheme for the restricted shortest path problem ⋮ Facility location with dynamic distance functions ⋮ The determination of the path with minimum-cost norm value ⋮ Approximation algorithms for multi-agent scheduling to minimize total weighted completion time ⋮ Approximate Pareto sets of minimal size for multi-objective optimization problems ⋮ Label correcting methods to solve multicriteria shortest path problems ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ Maximum probabilistic all-or-nothing paths ⋮ Bulk-robust combinatorial optimization ⋮ Min-max and min-max regret versions of combinatorial optimization problems: A survey ⋮ Efficiently Generating k-Best Solutions to Procurement Auctions ⋮ Modifying edges of a network to obtain short subgraphs ⋮ Implementing an efficient fptas for the 0-1 multi-objective knapsack problem ⋮ An empirical investigation of some bicriterion shortest path algorithms ⋮ Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function ⋮ Bicriterion Shortest Paths in Stochastic Time-Dependent Networks ⋮ Bicriteria Network Design Problems ⋮ Approximating the weight of shallow Steiner trees ⋮ Improved approximation algorithms for the combination problem of parallel machine scheduling and path ⋮ Stack-up algorithms for palletizing at delivery industry ⋮ An improved FPTAS for Restricted Shortest Path. ⋮ Approximate tradeoffs on weighted labeled matroids ⋮ Unnamed Item ⋮ Efficiently computing succinct trade-off curves ⋮ Time-dependent shortest paths through a fixed sequence of nodes: application to a travel planning problem ⋮ On budget-constrained flow improvement. ⋮ Approximation algorithms for multi-parameter graph optimization problems ⋮ An interactive procedure using domination cones for bicriterion shortest path problems ⋮ A parametric approach to solving bicriterion shortest path problems ⋮ When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem ⋮ A combination of flow shop scheduling and the shortest path problem
This page was built for publication: Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
