ACO The ACO Seminar (2011-2012)

Feb 2, 3:30pm, Wean 8220
Richard Peng, CMU
Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming


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.

Back to the ACO home page