The Taub Faculty of Computer Science Events and Talks
Noa Elad (M.Sc. Thesis Seminar)
Wednesday, 13.05.2015, 14:30
Advisor: Prof. Joseph (Seffi) Naor
We define a new class of semi-definite programs in which
the input arrives online. We use the primal dual method
to develop an algorithm for this setting of semi-definite
programs while maintaining the monotonicity requirements
of an online algorithm. Our algorithm achieves logarithmic
competitive ratios for both the primal and dual problems.
We will discuss applications from quantum information
theory, such as the Quantum Hypergraph Covering problem,
and also observe the behavior of this algorithm on well
studied problems such as Max Cut and Set Cover.