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

DOI10.1007/978-3-540-74208-1_6zbMATH Open1171.90516arXiv0805.2646OpenAlexW1599622173MaRDI QIDQ3603457FDOQ3603457

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)

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.

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

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

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)

Cited In (26)

• The smoothed number of Pareto-optimal solutions in bicriteria integer optimization
• Approximation with a fixed number of solutions of some multiobjective maximization problems
• 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
• Approximating multiobjective optimization problems: how exact can you be?
• Analysis of FPTASes for the multi-objective shortest path problem
• Decision-making based on approximate and smoothed Pareto curves
• Algorithms and Computation
• Fundamentals of Computation Theory
• Lower bound sets for biobjective shortest path problems
• Title not available (Why is that?)
• Small approximate Pareto sets for biobjective shortest paths and other problems
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• \(\epsilon\)-optimality for bicriteria programs and its application to minimum cost flows
• On the cardinality of the Pareto set in bicriteria shortest path problems
• Approximation with a fixed number of solutions of some biobjective maximization problems
• Title not available (Why is that?)
• A general approximation method for bicriteria minimization problems
• Computational complexity of finding Pareto efficient outcomes for biobjective lot-sizing models
• Approximating biobjective minimization problems using general ordering cones
• Efficiently computing succinct trade-off curves

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)