Analysis of FPTASes for the multi-objective shortest path problem

DOI10.1016/j.cor.2016.06.022zbMath1391.90600OpenAlexW2461759988MaRDI QIDQ1652052

Thomas Breugem, Twan Dollevoet, Wilco van den Heuvel

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: http://repub.eur.nl/pub/79908

zbMATH Keywords

multi-objective optimizationshortest path problemcomplexity analysisFPTAS

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Multi-objective and goal programming (90C29) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items (7)

Simple paths with exact and forbidden lengths ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ An improved multiobjective shortest path algorithm ⋮ Simple and efficient bi-objective search algorithms via fast dominance checks ⋮ A biobjective Dijkstra algorithm ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ Ant Lion Optimized Lexicographic Model for Shortest Path Identification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem
• Survey of multi-objective optimization methods for engineering
• A parametric approach to solving bicriterion shortest path problems
• Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications
• A comparison of solution strategies for biobjective shortest path problems
• Quadratic programming and combinatorial minimum weight product problems
• On the cardinality of the Pareto set in bicriteria shortest path problems
• Shortest-path algorithms: Taxonomy and annotation
• Faster algorithms for the shortest path problem
• A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
• Smoothed analysis of algorithms
• Multi‐objective combinatorial optimization problems: A survey
• Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms
• Multicriteria Optimization
• Computational Complexity
• The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization
• A lower bound for the shortest path problem

This page was built for publication: Analysis of FPTASes for the multi-objective shortest path problem