Monday, January 23, 2012
Freie Universität Berlin
Institut für Informatik
Takustraße 9 136, 14195 Berlin
room 005
Lecture - 14:15
Abstract:
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
Abstract:
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