文章基本信息

标题：Online Semidefinite Programming
本地全文：下载
作者：Noa Elad ; Satyen Kale ; Joseph 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：40:1-40:13
DOI：10.4230/LIPIcs.ICALP.2016.40
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider semidefinite programming through the lens of online algorithms - what happens if not all input is given at once, but rather iteratively? In what way does it make sense for a semidefinite program to be revealed? We answer these questions by defining a model for online semidefinite programming. This model can be viewed as a generalization of online coveringpacking linear programs, and it also captures interesting problems from quantum information theory. We design an online algorithm for semidefinite programming, utilizing the online primaldual method, achieving a competitive ratio of O(log(n)), where n is the number of matrices in the primal semidefinite program. We also design an algorithm for semidefinite programming with box constraints, achieving a competitive ratio of O(log F*), where F* is a sparsity measure of the semidefinite program. We conclude with an online randomized rounding procedure.
关键词：online algorithms; semidefinite programming; primal-dual