Monday, January 23, 2012
Freie Universität Berlin
Institut für Informatik
Takustraße 9 136, 14195 Berlin
Lecture - 14:15
Convex algebraic geometry, the fusion of convex geometry and (real) algebraic geometry, is a relatively young field which draws its motivation from the increasing need for (convex) optimization with polynomial constraints. In this talk I want to give an introduction to the fascinating world of convex algebraic geometry and, in particular, discuss its intimate relations to discrete geometry. To that end, I will introduce spectrahedra (the geometry underlying semidefinite programming) and their relation to polyhedra, and I will discuss the conjecturally larger class of hyperbolicity cones and their relation to (realizable) matroids. The emphasis is on geometry and most of the algebra will be linear.
Colloquium - 16:00
The minimum-weight set cover problem is widely known to be O(\log n)-approximable, with no improvement possible in the general case. We take the approach of exploiting problem structure to achieve better results, by providing a geometry-inspired algorithm whose approximation guarantee depends solely on an instance-specific combinatorial property known as shallow cell complexity (SCC).. Roughly speaking, a set cover instance has low SCC if any column-induced submatrix of the corresponding element-set incidence matrix has few distinct rows. By adapting and improving Varadarajan's recent quasi-uniform random sampling method for weighted geometric covering problems, we obtain strong approximation algorithms for a structurally rich class of weighted covering problems with low SCC.
Joint work with T. Chan, E. Grant & M. Sharpe