We give a simple O(log K / loglog K) approximation algorithm for the min-max selecting items problem. Since this number is the integrality gap of the LP formulation by Kasperski and Zieli\'nski (Annals OR (2009)), it is unlikely that LP-based methods can lead to better results. If time permits, I will also show how to make the approximation algorithm run in the RAM model of computation, that is, avoiding the assumption that rational powers of integers can be computed with arbitrary precision in constant time.
Benjamin Doerr, 04/19/2013 08:53
Benjamin Doerr, 04/18/2013 07:09
Benjamin Doerr, 04/17/2013 20:04
Benjamin Doerr, 04/17/2013 20:02 -- Created document.