The power of the weighted sum scalarization for approximating multiobjective optimization problems
From MaRDI portal
Publication:2075396
Abstract: We determine the power of the weighted sum scalarization with respect to the computation of approximations for general multiobjective minimization and maximization problems. Additionally, we introduce a new multi-factor notion of approximation that is specifically tailored to the multiobjective case and its inherent trade-offs between different objectives. For minimization problems, we provide an efficient algorithm that computes an approximation of a multiobjective problem by using an exact or approximate algorithm for its weighted sum scalarization. In case that an exact algorithm for the weighted sum scalarization is used, this algorithm comes arbitrarily close to the best approximation quality that is obtainable by supported solutions - both with respect to the common notion of approximation and with respect to the new multi-factor notion. Moreover, the algorithm yields the currently best approximation results for several well-known multiobjective minimization problems. For maximization problems, however, we show that a polynomial approximation guarantee can, in general, not be obtained in more than one of the objective functions simultaneously by supported solutions.
Recommendations
- Approximation methods for multiobjective and parametric optimization problems
- scientific article; zbMATH DE number 1830735
- Approximation with a fixed number of solutions of some multiobjective maximization problems
- Approximating multiobjective knapsack problems
- scientific article; zbMATH DE number 1830716
Cites work
- scientific article; zbMATH DE number 5764846 (Why is no real title available?)
- scientific article; zbMATH DE number 1530340 (Why is no real title available?)
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- A Greedy Heuristic for the Set-Covering Problem
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- A general approximation method for bicriteria minimization problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximability and Hardness in Multi-objective Optimization
- Approximate Pareto sets of minimal size for multi-objective optimization problems
- Approximation Methods for Multiobjective Optimization Problems: A Survey
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation with a fixed number of solutions of some multiobjective maximization problems
- Efficiently computing succinct trade-off curves
- How good is the Chord algorithm?
- Multicriteria Optimization
- One-exact approximate Pareto sets
- Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
- Small approximate Pareto sets for biobjective shortest paths and other problems
Cited in
(10)- Correction to: ``Pareto optimization or cascaded weighted sum: a comparison of concepts
- Weighted sum model with partial preference information: application to multi-objective optimization
- Advances in multiobjective optimisation: scalarisation, approximation, and complexity
- A weighting subgradient algorithm for multiobjective optimization
- Using scalarizations for the approximation of multiobjective optimization problems: towards a general theory
- An inner approximation method to compute the weight set decomposition of a triobjective mixed-integer problem
- On the linear weighted sum method for multi-objective optimization
- Approximation methods for multiobjective and parametric optimization problems
- Weighted Multidimensional Search and Its Application to Convex Optimization
- Approximating biobjective minimization problems using general ordering cones
This page was built for publication: The power of the weighted sum scalarization for approximating multiobjective optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2075396)
