Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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