|
Most combinatorial optimization problems are NP-hard, that is, they cannot be solved in polynomial time unless P is equal to NP. As a result, for over three decades, researchers have attempted to derive approximation algorithms that provide in polynomial time suboptimal solutions with a guarantee/proof of their degree of suboptimality. In the last fifteen years, there has been major progress on new techniques (deterministic and randomized roundings, semidefinite programming, embedding of finite metric spaces, etc.) for the design and analysis of these approximation algorithms, and also on negative results or the limit to approximability (through probabilistically checkable proofs and the PCP theorem). For example, a recent result of Khot, Kindler, Mossel and O’Donnell [2005] shows that, modulo the unique games conjecture, any improvement to the semidefinite programming based 0.87856-approximation algorithm of Goemans and Williamson [1995] for the maximum cut problem would imply that P is equal to NP. The workshop will include lectures on the latest developments in the field of approximation algorithms, on both the approximability and the inapproximability sides. INVITED SPEAKERS Matthew Andrews (Bell Labs) |