דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
נועה אלעד (הרצאה סמינריונית למגיסטר)
event date icon
יום רביעי, 13.05.2015, 14:30
event location icon
Taub 601
event speaker icon
מנחה: 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.