Combinatorial optimization problems with uncertain costs and the OWA criterion
From MaRDI portal
(Redirected from Publication:482291)
Abstract: In this paper a class of combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing distinct cost scenarios. The Ordered Weighted Averaging (OWA for short) aggregation operator is applied to choose a solution. The well-known criteria such as: the maximum, minimum, average, Hurwicz and median are special cases of OWA. By using OWA, the traditional min-max approach to combinatorial optimization problems with uncertain costs, often regarded as too conservative, can be generalized. The computational complexity and approximability of the problem of minimizing OWA for the considered class of problems are investigated and some new positive and negative results in this area are provided. These results remain valid for many important problems, such as network or resource allocation problems.
Recommendations
- Approximating combinatorial optimization problems with uncertain costs and the OWA criterion
- Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion
- Robust discrete optimization problems with the WOWA criterion
- Using the WOWA operator in robust discrete optimization problems
- Approximating combinatorial optimization problems with the ordered weighted averaging criterion
Cites work
- scientific article; zbMATH DE number 3137856 (Why is no real title available?)
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- scientific article; zbMATH DE number 1979522 (Why is no real title available?)
- scientific article; zbMATH DE number 3410784 (Why is no real title available?)
- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
- A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid
- A randomized algorithm for the min-Max selecting items problem with uncertain weights
- Approximating the min-max (regret) selecting items problem
- Choquet-based optimisation in multiobjective shortest path and spanning tree problems
- Complexity of the min-max (regret) versions of min cut problems
- 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
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Network flows. Theory, algorithms, and applications.
- On ordered weighted averaging aggregation operators in multicriteria decisionmaking
- On solving linear programs with the ordered weighted averaging objective.
- On the approximability of minmax (regret) network optimization problems
- On the approximability of robust spanning tree problems
- On the complexity of a class of combinatorial optimization problems with uncertainty
- On the robust shortest path problem.
- Robust discrete optimization and its applications
- Robust discrete optimization and network flows
- Robust optimization
- The Minimum Satisfiability Problem
Cited in
(15)- Robust optimization with belief functions
- Robust discrete optimization problems with the WOWA criterion
- Robust single machine scheduling problem with weighted number of late jobs criterion
- Ordered weighted average optimization in multiobjective spanning tree problem
- Robust optimization with scenarios using belief functions
- Approximating combinatorial optimization problems with the ordered weighted averaging criterion
- Using the WOWA operator in robust discrete optimization problems
- Solving linear unconstrained problems of combinatorial optimization on arrangements under stochastic uncertainty
- Combinatorial optimization under uncertainty
- Bottleneck combinatorial optimization problems with fuzzy scenarios
- Choquet integral optimisation with constraints and the buoyancy property for fuzzy measures
- Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case
- Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion
- Approximating combinatorial optimization problems with uncertain costs and the OWA criterion
- Anytime algorithms for adaptive robust optimization with OWA and WOWA
This page was built for publication: Combinatorial optimization problems with uncertain costs and the OWA criterion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482291)
