#
Monday Lecture and Colloquium

**Monday, January 23, 2012**

Freie Universität Berlin

Institut für Informatik

Takustraße 9 136, 14195 Berlin

room 005

** Lecture - 14:15**

### Raman Sanyal - FU Berlin

### Discrete and convex algebraic geometry

*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**

###
Jochen Könemann - University of Waterloo

###
Solving Structured Set Cover Instances via Geometric Sampling

*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

Letzte Aktualisierung:
17.01.2012