Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems

DOI10.1007/978-3-540-74208-1_6MaRDI QIDQ3603457zbMATH OpenOpenAlexFDO

Authors Ilias Diakonikolas, Mihalis Yannakakis

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.2646

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy $epsilon$ the Pareto curve of a multiobjective optimization problem. We show that for a broad class of bi-objective problems (containing many important widely studied problems such as shortest paths, spanning tree, and many others), we can compute in polynomial time an $epsilon$-Pareto set that contains at most twice as many solutions as the minimum such set. Furthermore we show that the factor of 2 is tight for these problems, i.e., it is NP-hard to do better. We present upper and lower bounds for three or more objectives, as well as for the dual problem of computing a specified number $k$ of solutions which provide a good approximation to the Pareto curve.

Recommendations

• Small approximate Pareto sets for biobjective shortest paths and other problems
• Approximate Pareto sets of minimal size for multi-objective optimization problems
• One-exact approximate Pareto sets
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximation with a fixed number of solutions of some biobjective maximization problems

Cited in

(26)

• Approximation with a fixed number of solutions of some multiobjective maximization problems
• The smoothed number of Pareto-optimal solutions in bicriteria integer optimization
• Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications
• Approximate Pareto sets of minimal size for multi-objective optimization problems
• Framing algorithms for approximate multicriteria shortest paths
• New polynomial time algorithms to compute a set of Pareto optimal paths for multi-objective shortest path problems
• Generalized nash fairness solutions for bi‐objective minimization problems
• Minimum effort approximation of the Pareto space of convex bi-criteria problems
• One-exact approximate Pareto sets
• Analysis of FPTASes for the multi-objective shortest path problem
• Decision-making based on approximate and smoothed Pareto curves
• Approximating multiobjective optimization problems: how exact can you be?
• Algorithms and Computation
• Lower bound sets for biobjective shortest path problems
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 1830716 (Why is no real title available?)
• Small approximate Pareto sets for biobjective shortest paths and other problems
• \(\epsilon\)-optimality for bicriteria programs and its application to minimum cost flows
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• On the cardinality of the Pareto set in bicriteria shortest path problems
• Approximation with a fixed number of solutions of some biobjective maximization problems
• scientific article; zbMATH DE number 1848402 (Why is no real title available?)
• A general approximation method for bicriteria minimization problems
• Computational complexity of finding Pareto efficient outcomes for biobjective lot-sizing models
• Efficiently computing succinct trade-off curves
• Approximating biobjective minimization problems using general ordering cones

This page was built for publication: Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems

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