We consider the robust version of items selection problem, in which the goal is to choose representatives from a family of sets, preserving constraints on the allowed items' combinations. We prove NP-hardness of the deterministic version, and establish polynomially solvable special cases. Next, we consider the robust version in which we aim at minimizing the maximum regret of the solution under interval parameter uncertainty. We show that this problem is hard for the second level of polynomial-time hierarchy. We develop an exact solution algorithm for the robust problem, based on cut generation, and present the results of computational experiments.
Note that deterministic version of Representatives Selection Problem is easily solvable in polynomial time. For interval uncertainty representation of cost parameters the problem can still be solved in polynomial time, both in case of minimizing the maximum regret and the relative regret @cite_8 . However, in case of discrete set of scenarios, the problem becomes NP-hard even for 2 scenarios, and strongly NP-hard when the number of scenarios @math is a part of the input. In @cite_6 authors prove that strong NP-hardness holds also when sets of eligible items are bounded. In @cite_2 an @math -approximation algorithm for this variant was given.
@cite_2 @cite_6 @cite_8
2027995829 2044046971 2029243025 2153675120
In this paper new complexity and approximation results on the robust versions of the representatives selection problem, under the scenario uncertainty representation, are provided, which extend the results obtained in the recent papers by Dolgui and Kovalev (2012) and Deineko and Woeginger (2013). Namely, it is shown that if the number of scenarios is a part of input, then the min-max (regret) representatives selection problem is not approximable within a ratio of O ( log 1 - ? K ) for any ? > 0 , where K is the number of scenarios, unless the problems in NP have quasi-polynomial time algorithms. An approximation algorithm with an approximation ratio of O ( log K log log K ) for the min-max version of the problem is also provided. The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min–max and min–max (relative) regret approaches are used for making a selection decision. The arising min–max, min–max regret and min–max relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line. We establish strong NP-hardness and in-approximability of the so-called representatives selection problem, a tool selection problem in the area of robust optimization. Our results answer a recent question of Dolgui and Kovalev (4OR Q J Oper Res 10:181–192, 2012). The minmax regret problem for combinatorial optimization under uncertainty can be viewed as a zero-sum game played between an optimizing player and an adversary, where the optimizing player selects a solution and the adversary selects costs with the intention of maximizing the regret of the player. The conventional minmax regret model considers only deterministic solutions strategies, and minmax regret versions of most polynomial solvable problems are NP-hard. In this paper, we consider a randomized model where the optimizing player selects a probability distribution (corresponding to a mixed strategy) over solutions and the adversary selects costs with knowledge of the player’s distribution, but not its realization. We show that under this randomized model, the minmax regret version of any polynomial solvable combinatorial problem becomes polynomial solvable. This holds true for both interval and discrete scenario representations of uncertainty. Using the randomized model, we show new proofs of existing approximation algorithms for the deterministic model based on primal-dual approaches. We also determine integrality gaps of minmax regret formulations, giving tight bounds on the limits of performance gains from randomization. Finally, we prove that minmax regret problems are NP-hard under general convex uncertainty.