Approximating biobjective minimization problems using general ordering cones

DOI10.1007/S10898-023-01276-XMaRDI QIDQ6162511zbMATH OpenOpenAlexFDO

Authors Arne Herzel, Stephan Helfrich, Stefan Ruzika, Clemens Thielen

Publication date 28 June 2023

Published in Journal of Global Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

efficient solutionmultiobjective optimizationordering coneapproximate Pareto setsupported solution

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Approximation algorithms (68W25)

Abstract: This article investigates the approximation quality achievable for biobjective minimization problems with respect to the Pareto cone by solutions that are (approximately) optimal with respect to larger ordering cones. When simultaneously considering $alpha$-approximations for all closed convex ordering cones of a fixed inner angle $gammain[fracpi2,pi]$, an approximation guarantee between $alpha$ and $2alpha$ is achieved, which depends continuously on $gamma$. The analysis is best-possible for any inner angle and it generalizes and unifies the known results that the set of supported solutions is a 2-approximation and that the efficient set itself is a 1-approximation. Moreover, it is shown that, for maximization problems, no approximation guarantee is achievable by considering larger ordering cones in the described fashion, which again generalizes a known result about the set of supported solutions.

Recommendations

• Approximation methods for multiobjective and parametric optimization problems
• A general approximation method for bicriteria minimization problems
• Approximation with a fixed number of solutions of some biobjective maximization problems
• Small approximate Pareto sets for biobjective shortest paths and other problems
• Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems

Cites work

• scientific article; zbMATH DE number 5764846 (Why is no real title available?)
• A general approximation method for bicriteria minimization problems
• Advances in Cone-Based Preference Modeling for Decision Making with Multiple Criteria
• Approximability and Hardness in Multi-objective Optimization
• Approximate Pareto sets of minimal size for multi-objective optimization problems
• Approximately dominating representatives
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• Cone characterizations of approximate solutions in real vector optimization
• Cone convexity, cone extreme points, and nondominated solutions in decision problems with multiobjectives
• Covers and approximations in multiobjective optimization
• Efficiently computing succinct trade-off curves
• How good is the Chord algorithm?
• Multicriteria Optimization
• Multiple-criteria decision making. Concepts, techniques, and extensions. With the assistance of Yoon-Ro Lee and Antonie Stam
• One-exact approximate Pareto sets
• Recent Developments in Vector Optimization
• Relative importance of criteria in multiobjective programming: a cone-based approach
• Relative importance of criteria: a quantitative approach
• Small approximate Pareto sets for biobjective shortest paths and other problems
• The power of the weighted sum scalarization for approximating multiobjective optimization problems
• Vector optimization problems and their solution concepts

Cited in

(2)

• Using scalarizations for the approximation of multiobjective optimization problems: towards a general theory
• Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach

This page was built for publication: Approximating biobjective minimization problems using general ordering cones

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