|
|
MIT Electrical Engineering and Computer Science
EECS Event |
Tuesday, November 7, 2000
4:00 PM (reception following)
Room 35-225
LIDS Colloquium
Abstract
In this talk, I will first give a general overview of semidefinite programming and approximation algorithms. I will then propose the use of semidefinite programming over complex Hermitian matrices to design approximation algorithms for certain combinatorial optimization problems. In particular, I will illustrate it by showing that for the problem of maximizing the number of satisfied (in)equations modulo 3 with 2 variables per (in)equation, complex semidefinite programming can be used to derive an approximation algorithm.