Improved approximation algorithms for the MinMax Selecting Items problem
We give a simple deterministic O ( log K / log log K ) approximation algorithm for the MinMax Selecting Items problem with K scenarios. It improves over the previous best approximation ratio of O ( log K ) due to Kasperski, Kurpisz, and Zielinski (2013) [4]. It has a polynomial runtime also in the RAM model of computation. We also show that the standard LP formulation for this problem has an integrality gap of order log K / log log K . Dependent randomized rounding is the main tool.
approximation algorithm randomized rounding derandomization robust optimization