Online Semidefinite Programming

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



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.40.pdf
  • Filesize: 458 kB
  • 13 pages

Document Identifiers

Author Details

Noa Elad
Satyen Kale
Joseph (Seffi) Naor

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ICALP.2016.40

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.
Keywords
  • online algorithms
  • semidefinite programming
  • primal-dual

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Rudolf Ahlswede and Andreas Winter. Strong converse for identification via quantum channels. Information Theory, IEEE Transactions on, 48(3):569-579, 2002. Google Scholar
  2. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. cambridge university press, 2005. Google Scholar
  3. Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34(2):270-286, 2009. Google Scholar
  4. Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115-1145, 1995. Google Scholar
  5. Anupam Gupta and Viswanath Nagarajan. Approximating sparse covering integer programs online. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 436-448, 2012. Google Scholar
  6. Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389-434, 2012. Google Scholar
  7. Avi Wigderson and David Xiao. Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail