Approximating combinatorial optimization problems with the ordered weighted averaging criterion
From MaRDI portal
Abstract: The paper deals with a multiobjective combinatorial optimization problem with linear cost functions. The popular Ordered Weighted Averaging (OWA) criterion is used to aggregate the cost functions and compute a solution. It is well known that minimizing OWA for most basic combinatorial problems is weakly NP-hard even if the number of objectives equals two, and strongly NP-hard when is a part of the input. In this paper, the problem with nonincreasing weights in the OWA criterion and a large is considered. A method of reducing the number of objectives by appropriately aggregating the objective costs before solving the problem is proposed. It is shown that an optimal solution to the reduced problem has a guaranteed worst-case approximation ratio. Some new approximation results for the Hurwicz criterion, which is a special case of OWA, are also presented.
Recommendations
- Approximating combinatorial optimization problems with uncertain costs and the OWA criterion
- Combinatorial optimization problems with uncertain costs and the OWA criterion
- Robust discrete optimization problems with the WOWA criterion
- Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion
- Ordered weighted average combinatorial optimization: formulations and their properties
Cites work
- scientific article; zbMATH DE number 6009887 (Why is no real title available?)
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- scientific article; zbMATH DE number 663895 (Why is no real title available?)
- A Sample Approximation Approach for Optimization with Probabilistic Constraints
- A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
- A survey and annotated bibliography of multiobjective combinatorial optimization
- Alternative formulations for the ordered weighted averaging objective
- Analytic Inequalities
- Approximating the Pareto optimal set using a reduced set of objective functions
- Combinatorial optimization problems with uncertain costs and the OWA criterion
- Commitment under uncertainty: Two-stage stochastic matching problems
- Constructing uncertainty sets for robust linear optimization
- Criteria and dimension reduction of linear multiple criteria optimization problems
- Equitable aggregations and multiple criteria analysis
- Exact algorithms for OWA-optimization in multiobjective spanning tree problems
- General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
- Improved approximation algorithms for the Min-Max selecting items problem
- Inequality measures and equitable approaches to location problems
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Minimizing the sum of the \(k\) largest functions in linear time.
- Multicriteria Optimization
- Multi‐objective combinatorial optimization problems: A survey
- On ordered weighted averaging aggregation operators in multicriteria decisionmaking
- On scenario aggregation to approximate robust combinatorial optimization problems
- On solving linear programs with the ordered weighted averaging objective.
- Ordered weighted average combinatorial optimization: formulations and their properties
- Ordered weighted average optimization in multiobjective spanning tree problem
- Preprocessing and cut generation techniques for multi-objective binary programming
- Redundant objective functions in linear vector maximum problems and their determination
- Robust discrete optimization and its applications
- Scenarios and Policy Aggregation in Optimization Under Uncertainty
- Simple greedy algorithms for fundamental multidimensional graph problems
- Stochastic linear programming. Models, theory, and computation
- Using the WOWA operator in robust discrete optimization problems
Cited in
(14)- A unified pre-training and adaptation framework for combinatorial optimization on graphs
- Benchmarking problems for robust discrete optimization
- Robust min-max (regret) optimization using ordered weighted averaging
- Approximating optimization problems in graphs with locational uncertainty
- Ordered weighted average combinatorial optimization: formulations and their properties
- scientific article; zbMATH DE number 4016556 (Why is no real title available?)
- Optimizing three-dimensional constrained ordered weighted averaging aggregation problem with bounded variables
- A three-dimensional constrained ordered weighted averaging aggregation problem with lower bounded variables
- On solving linear programs with the ordered weighted averaging objective.
- Combinatorial optimization problems with uncertain costs and the OWA criterion
- Choquet integral optimisation with constraints and the buoyancy property for fuzzy measures
- On Solving Optimization Problems with Ordered Average Criteria and Constraints
- Alternative formulations for the ordered weighted averaging objective
- Approximating combinatorial optimization problems with uncertain costs and the OWA criterion
This page was built for publication: Approximating combinatorial optimization problems with the ordered weighted averaging criterion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189877)
