DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2016.40

Online Semidefinite Programming

Authors: Noa Elad, Satyen Kale, and Joseph (Seffi) Naor

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract

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.

Cite as

Noa Elad, Satyen Kale, and Joseph (Seffi) Naor. Online Semidefinite Programming. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{elad_et_al:LIPIcs.ICALP.2016.40,
  author =	{Elad, Noa and Kale, Satyen and Naor, Joseph (Seffi)},
  title =	{{Online Semidefinite Programming}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{40:1--40:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.40},
  URN =		{urn:nbn:de:0030-drops-63205},
  doi =		{10.4230/LIPIcs.ICALP.2016.40},
  annote =	{Keywords: online algorithms, semidefinite programming, primal-dual}
}

Search Results

Documents authored by Elad, Noa

Online Semidefinite Programming

Abstract

Cite as

Thanks for your feedback!

Could not send message