Semidefinite programs are generalizations of linear programs that play a
key role in many optimization problems. The special case where all matrices
in the constraints and objective are positive semidefinite can also be
viewed as a generalization of positive linear programs. Recently, Jain and
Yao gave an algorithm that produces an (1+eps) approximation in
((log n)/eps)^13
iterations for this case, bringing the problem to NC.
We present a simpler NC parallel algorithm that requires O(((log n)/eps)^4
log(1/eps)) iterations. Moreover, if the positive SDP is provided
in a factorized form, the total work of our algorithm is nearly linear.
This is ongoing work with Kanat Tangwongsan.
The ACO Seminar (2011-2012)