DocumentCode :
2723354
Title :
A Parallel Approximation Algorithm for Positive Semidefinite Programming
Author :
Jain, Rahul ; Yao, Penghui
Author_Institution :
Dept. of Comput. Sci., Nat. Univ. of Singapore, Singapore, Singapore
fYear :
2011
fDate :
22-25 Oct. 2011
Firstpage :
463
Lastpage :
471
Abstract :
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].
Keywords :
approximation theory; linear programming; parallel algorithms; approximation factor; multiplicative factor; parallel approximation algorithm; parallel time polygon; positive linear programs; positive semidefinite programming; Algorithm design and analysis; Approximation algorithms; Approximation methods; Bismuth; Eigenvalues and eigenfunctions; Matrix decomposition; Yttrium; Fast parallel algorithms; multiplicative weight update; positive semidefinite programming;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on
Conference_Location :
Palm Springs, CA
ISSN :
0272-5428
Print_ISBN :
978-1-4577-1843-4
Type :
conf
DOI :
10.1109/FOCS.2011.25
Filename :
6108207
Link To Document :
بازگشت