Please use this identifier to cite or link to this item: https://doi.org/10.1109/FOCS.2011.25
Title: A parallel approximation algorithm for positive semidefinite programming
Authors: Jain, R. 
Yao, P.
Keywords: Fast parallel algorithms
multiplicative weight update
positive semidefinite programming
Issue Date: 2011
Source: Jain, R., Yao, P. (2011). A parallel approximation algorithm for positive semidefinite programming. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS : 463-471. ScholarBank@NUS Repository. https://doi.org/10.1109/FOCS.2011.25
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]. © 2011 IEEE.
Source Title: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
URI: http://scholarbank.nus.edu.sg/handle/10635/41152
ISBN: 9780769545714
ISSN: 02725428
DOI: 10.1109/FOCS.2011.25
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

12
checked on Dec 7, 2017

WEB OF SCIENCETM
Citations

3
checked on Nov 22, 2017

Page view(s)

40
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.