期刊
THEORETICAL COMPUTER SCIENCE
卷 565, 期 -, 页码 102-112出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2014.11.013
关键词
Combinatorial optimization; OWA operator; Robust optimization; Computational complexity; Approximation algorithms
资金
- National Center for Science (Narodowe Centrum Nauki) [2013/09/B/ST6/01525]
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. Some well known criteria used in decision making under uncertainty such as the maximum, minimum, average, Hurwicz and median are special cases of OWA. Furthermore, by using OWA, the traditional robust (min-max) approach to combinatorial optimization problems with uncertain costs 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 basic problems, such as network or resource allocation problems. (C) 2014 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据