Cliff Stein

Feasible and accurate algorithms for covering semidefinite programs

  • Garud Iyengar
  • Cliff Stein
  • David Phillips
    • Categories Approximation Algorithms, Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    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 … Read more

    Approximating semidefinite packing problems

  • Garud Iyengar
  • Cliff Stein
  • David Phillips
    • Categories Approximation Algorithms, Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    In this paper we define semidefinite packing programs and describe an algorithm to approximately solve these problems. Semidefinite packing programs arise in many applications such as semidefinite programming relaxations for combinatorial optimization problems, sparse principal component analysis, and sparse variance unfolding technique for dimension reduction. Our algorithm exploits the structural similarity between semidefinite packing programs … Read more