Combinatorial optimization problems with uncertain costs and the OWA criterion

DOI10.1016/J.TCS.2014.11.013zbMATH Open1315.90037arXiv1305.5339OpenAlexW1976995845MaRDI QIDQ482291FDOQ482291

Authors: Adam Kasperski, Paweł Zieliński 

Publication date: 22 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

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 $K$ 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.

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

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

zbMATH Keywords

computational complexitycombinatorial optimizationapproximation algorithmsrobust optimizationOWA operator

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Robust optimization
• Title not available (Why is that?)
• On ordered weighted averaging aggregation operators in multicriteria decisionmaking
• Robust discrete optimization and its applications
• On the robust shortest path problem.
• Robust discrete optimization and network flows
• Title not available (Why is that?)
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Exact algorithms for OWA-optimization in multiobjective spanning tree problems
• On solving linear programs with the ordered weighted averaging objective.
• Approximating the min-max (regret) selecting items problem
• The Minimum Satisfiability Problem
• Title not available (Why is that?)
• A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid
• On the complexity of a class of combinatorial optimization problems with uncertainty
• Complexity of the min-max (regret) versions of min cut problems
• Choquet-based optimisation in multiobjective shortest path and spanning tree problems
• A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
• Title not available (Why is that?)
• General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
• On the approximability of robust spanning tree problems
• On the approximability of minmax (regret) network optimization problems
• A randomized algorithm for the min-Max selecting items problem with uncertain weights
• Improved approximation algorithms for the Min-Max selecting items problem

Cited In (11)

• 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
• Robust Discrete Optimization Problems with the WOWA Criterion
• Using the WOWA operator in robust discrete optimization problems
• Solving linear unconstrained problems of combinatorial optimization on arrangements under stochastic uncertainty
• Robust Single Machine Scheduling Problem with Weighted Number of Late Jobs Criterion
• Combinatorial optimization under uncertainty
• 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
• Robust optimization with belief functions

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)