MIN-MAX-MIN OPTIMIZATION WITH SMOOTH AND STRONGLY CONVEX OBJECTIVES.

We consider min-max-min optimization with smooth and strongly convex objectives. Our motivation for studying this class of problems stems from its connection to the κ-center problem and the growing literature on min-max-min robust optimization. In particular, the considered class of problems nontrivially generalizes the Euclidean κ-center problem in the sense that distances in this more general setting do not necessarily satisfy metric properties. We present a 9κ-approximation algorithm (whereκ is the maximum condition number of the functions involved) that generalizes a simple greedy 2-approximation algorithm for the classical κ-center problem. We show that for any choice ofκ, there is an instance with a condition number ofκ per which our algorithm yields a (4κ+ 4κ + 1)-approximation guarantee, implying that our analysis is tight whenκ=1. Finally, we compare the computational performance of our approximation algorithm with an exact mixed integer linear programming approach. [ABSTRACT FROM AUTHOR]