The power of the weighted sum scalarization for approximating multiobjective optimization problems
From MaRDI portal
Publication:2075396
DOI10.1007/S00224-021-10066-5zbMATH Open1485.90121arXiv1908.01181OpenAlexW3216846121MaRDI QIDQ2075396FDOQ2075396
Authors: Cristina Bazgan, Stefan Ruzika, Clemens Thielen, Daniel Vanderpooten 
Publication date: 14 February 2022
Published in: Theory of Computing Systems (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1908.01181
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
Multi-objective and goal programming (90C29) Approximation methods and heuristics in mathematical programming (90C59)
Cites Work
- A Greedy Heuristic for the Set-Covering Problem
- Multicriteria Optimization
- Approximation algorithms for NP-complete problems on planar graphs
- A linear-time approximation algorithm for the weighted vertex cover problem
- Efficiently computing succinct trade-off curves
- Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
- Small approximate Pareto sets for biobjective shortest paths and other problems
- Title not available (Why is that?)
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Approximation with a fixed number of solutions of some multiobjective maximization problems
- Approximability and Hardness in Multi-objective Optimization
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Approximate Pareto sets of minimal size for multi-objective optimization problems
- A general approximation method for bicriteria minimization problems
- Title not available (Why is that?)
- One-exact approximate Pareto sets
- How good is the Chord algorithm?
- Approximation Methods for Multiobjective Optimization Problems: A Survey
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)
