In this paper we describe an algorithm to approximately solve a class of semidefinite programs called covering semidefinite programs. This class includes many semidefinite programs that arise in the context of developing algorithms for important optimization problems such as sparsest cut, wireless multicasting, and pattern classification. We give algorithms for covering SDPs whose dependence on $\eps$ is only $\eps^{-1}$. These algorithms, therefore, have a better dependence on $\eps$ than other combinatorial approaches, with a tradeoff of a somewhat worse dependence on the other parameters. For many reasons, including numerical stability and a variety of implementation concerns, the dependence on $\eps$ is critical, and the algorithms in this paper may be preferable to those of the previous work. Our algorithms exploit the structural similarity between covering semidefinite programs, packing semidefinite programs and packing and covering linear programs.
Citation
Proceedings of the 12th Scandinavian Workshop on Algorithms and Theory, pp. 150-162, 2010.