A Parallel Approximation Algorithm for Positive Semidefinite Programming

Positive semi definite programs are an important subclass of semi definite programs in which all matrices involved in the specification of the problem are positive semi definite and all scalars involved are non-negative. We present a parallel algorithm, which given an instance of a positive semi definite program of size N and an approximation factor ε >; 0, runs in (parallel) time poly(1/ε)·polylog(N), using poly(N) processors, and outputs a value which is within multiplicative factor of (1+ε) to the optimal. Our result generalizes analogous result of Luby and Nisan (1993) for positive linear programs and our algorithm is inspired by their algorithm of [10].

Authors

• Rahul Jain 0001
• Penghui Yao

Keywords

• Bismuth
• Eigenvalues and eigenfunctions
• Yttrium
• Approximation algorithms
• Algorithm design and analysis
• Approximation methods
• Matrix decomposition
• Positive Semidefinite
• Semidefinite Programming
• Parallel Algorithm
• Running Time
• Diagonal Matrix
• Positive Matrix
• Projector
• Positive Semidefinite Matrix
• Dual Variables
• Hermitian Matrix
• Eigenspace
• Primal Problem
• Large Eigenvalues
• Primal Variables
• Fast parallel algorithms
• positive semidefinite programming
• multiplicative weight update