On the polynomial solvability of distributionally robust k-sum optimization. (4th July 2017)

• Record Type: Journal Article
• Authors: Dhara, Anulekha; Natarajan, Karthik
• Is Part Of: Optimization methods and software. Volume 32:Number 4(2017)
• Page Start: 738
• Page End: 753
• Publication Date: 2017-07-04
• Subjects: robust optimization -- k sum optimization -- distributions; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1215447
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In this paper, we define a distributionally robust k -sum optimization problem as the problem of finding a solution that minimizes the worst-case expected sum of up to the k largest costs of the elements in the solution. The costs are random with a joint probability distribution that is not completely specified but rather assumed to be known to lie in a set of probability distributions. For k =1, this reduces to a distributionally robust bottleneck optimization problem while for k = n, this reduces to distributionally robust minimum sum optimization problem. Our main result is that for a Fréchet class of discrete marginal distributions with finite support, the distributionally robust k -sum combinatorial optimization problem is solvable in polynomial time if the deterministic minimum sum problem is solvable in polynomial time. This extends the result of Punnen and Aneja [ On k-sum optimization, Oper. Res. Lett. 18(5)(1996), pp. 233–236] from the deterministic to the robust case. We show that this choice of the set of distributions helps preserve the submodularity of the k -sum objective function which is an useful structural property for optimization problems.