Paper Info
Title
Approximating multiobjective combinatorial optimization problems with the OWA criterion.
Abstract
The paper deals with a multiobjective combinatorial optimization problem with $K$ 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 $K$ equals two, and strongly NP-hard when $K$ is a part of the input. In this paper, the problem with nonincreasing weights in the OWA criterion and a large $K$ 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.
Year
Venue
Field
2018
arXiv: Data Structures and Algorithms
Discrete mathematics,Mathematical optimization,Combinatorial optimization problem,Mathematics,Special case
DocType
Volume
Citations 
Journal
abs/1804.03594
0
PageRank 
References 
Authors
0.34
11
4
Name
Order
Citations
PageRank
André B. Chassein1567.80
Marc Goerigk27214.77
Adam Kasperski335233.64
Paweł Zieliński422728.62