M.Sc Thesis

M.Sc StudentElad Noa
SubjectOnline Semidefinite Programming
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor
Full Thesis textFull thesis text - English Version


Semidefinite programming is a useful tool through which complex problems can be expressed and solved. It is a natural generalization of linear programming, yet problems expressed in this form can provide tighter bounds on relaxations of combinatorial problems. For instance, in max cut - the problem of finding a maximal weight cut in a graph - the semidefinite programming relaxation allows an approximation ratio of 0.878, while linear programming relaxations cannot do better than 0.5.

Online algorithms model scenarios where we want to solve a problem without knowing the entire input in advance. Using the same example of max cut, in an online setting we might receive knowledge of the vertices of the graph one-by-one, and require the algorithm to maintain a large-weight cut of the vertices we already know. A defining feature of online algorithms is that they cannot revoke previously made decisions - so the cut that we already have cannot be changed, and we can only decide on future vertices - on which side of the cut will they go.

In this work we look at a general semidefinite program through the lens of online algorithms - what happens if the problem is not given all at once, but rather given in an iterative fashion? In what way does it make sense for the semidefinite program to be revealed? We answer these questions by defining a model for online semidefinite programming. This model captures the online max cut problem, as well as interesting problems from the field of quantum information theory. It can also be viewed as a generalization of online covering and packing.

We design an online algorithm for semidefinite programming, which utilizes the primal-dual method. The algorithm achieves a competitive ratio of O(log n), where n is the number of matrices in the primal semidefinite program. This ratio is optimal since it matches the competitive ratio of the online set cover problem, which is known to be optimal. We also design an algorithm for semidefinite programming with box constraints, which achieves a competitive ratio of O(log F), where F is a sparsity measure of the semidefinite program.