Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

Details Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

2012-01-24

arxiv.org/abs/1201.5135v1

Computer Science

Data Structures and Algorithms

Scientific paper

This paper studies the problem of finding a (1+eps)-approximation to positive semidefinite programs. These are semidefinite programs in which all matrices in the constraints and objective are positive semidefinite and all scalars are non-negative. Previous work (Jain and Yao, FOCS'11) gave an NC algorithm that requires at least Omega((1/eps)^13\log^{13}n) iterations. The algorithm performs at least Omega(n^\omega) work per iteration, where n is the dimension of the matrices involved, since each iteration involves computing spectral decomposition. We present a simpler NC parallel algorithm that requires O((1/eps)^4 \log^4 n \log(1/eps)) iterations. Moreover, if the positive SDP is provided in a factorized form, the total work of our algorithm can be bounded by \otilde(n+M), where M is the total number of nonzero entries in the factorization. Our algorithm is a generalization of Young's algorithm and analysis techniques for positive linear programs (Young, FOCS'01) to the semidefinite programming setting.

Affiliated with

Also associated with

No associations

Rating

Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-682671