Optimization Online


Feasible and accurate algorithms for covering semidefinite programs

Garud Iyengar(garud***at***ieor.columbia.edu)
David Phillips(phillips***at***math.wm.edu)
Cliff Stein(cliff***at***ieor.columbia.edu)

Abstract: 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.

Keywords: First-order methods, semidefinite programs, non-smooth optimization, combinatorial optimization

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Combinatorial Optimization (Approximation Algorithms )

Citation: Proceedings of the 12th Scandinavian Workshop on Algorithms and Theory, pp. 150-162, 2010.

Download: [PDF]

Entry Submitted: 07/02/2010
Entry Accepted: 07/05/2010
Entry Last Modified: 07/02/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society