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. Keywords: robust optimization, selection problem, uncertainty, computational complexity In [3, 6] the min-max and min-max regret versions of the following representatives selection problem (RS for short) have been recently discussed. We are given a set T of n tools, numbered from 1 to n. This set is partitioned into p disjoint sets T 1 , . . . , T p , where |T i | = r i and n = i∈ [p] r i (we use [p] to denote the set {1, . . . p}). We wish to choose a subset X ⊆ T of the tools that contains exactly one tool from each set T i , i.e. |X ∩ T i | = 1 for each i ∈ [p]. In the deterministic case, each tool j ∈ T has a nonnegative cost c j and we seek a solution X whose total cost F (X) = j∈X c j is minimal. This problem can be solved by a trivial algorithm, which chooses a tool of the smallest cost from each T i . An important problem characteristic is the maximal number of elements in T i , i.e. r max = max i∈[p] r i . We can assume that r i ≥ 2 for all i ∈ [p], since a subset with the cardinality of 1 can be ignored. It is easy to see that RS is a special case of the Shortest Path problem, and this fact is depicted in Figure 1 . Each solid arc in the graph G shown in Figure 1 corresponds to a tool in T i and each dummy (dashed) arc has zero cost. There is one-to-one correspondence between the s-t paths in G and the solutions to RS. It is not difficult to transform the network G and show that RS is also a special case of other basic network problems such as: Minimum Spanning Tree, Minimum Assignment, or Minimum Cut (see, e.g. [7] ).
In REF an O(log K/ log log K)-approximation algorithm for this variant was given.
Approximability of the robust representatives selection problem
ArXiv
ArXiv
Mathematics Computer Science