2026-07-24T18:10:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6320 2024-03-06T10:37:42Z ddc:004 open_access

Online Semidefinite Programming Elad, Noa Kale, Satyen Naor, Joseph (Seffi) online algorithms semidefinite programming primal-dual 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noa Elad and Satyen Kale and Joseph (Seffi) Naor 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.40 urn:nbn:de:0030-drops-63205 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.40 eng https://creativecommons.org/licenses/by/3.0/legalcode