“اخبار”

 پژوهشکده ریاضیات - 1393/8/8

دوره آموزشي

سلمان بيگي
پژوهشكده رياضيات
30 مهر، 1، 7 و 8 آبان ماه 1393

 
 



Abstract

In recent years semidefinite programming has been successfully applied in combinatorial optimization and design of algorithms. The flagship discoveries in this field are the Goemans-Williamson algorithm for MAXCUT, and Lovasz’s method for computing the Shannon capacity of a pentagon. This course is a short introduction to this field. This short course starts with a brief review of linear programming and its applications in combinatorial optimization. Then semidefinite programming is introduced and the algorithm of Goemans and Williamson is presented. Next the Lovasz theta function and its applications are reviewed. Finally implications of semidefinite programming for proving direct product theorems are discussed.



Information:


Date and Time: Wednesday, October 22 at 11:00-12:30
Thursday, October 23 at 9:00-10:30 and 15:30-17:00
Wednesday, October 29 at 11:00-12:30
Thursday, October 30 at 9:00-10:30 and 15:30-17:00
Place: Niavaran Bldg., Niavaran Square, Tehran, Iran
 
 
back to top
scroll left or right