Monday, January 17, 2011
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041
Lecture - 14:15
Abstract:
Several important combinatorial optimization problems such as shortest paths, polymatroid intersection, min-cost arborescences, etc.,
fit into the framework of Hoffman's lattice polyhedron model. An extension of the model to ternary matrices even covers submodular flows,
a far reaching generalization of mincost flows.
Lattice polyhedra are based on a lattice structure on the underlying matrix that obeys certain submodularity conditions. However, although lattice
polyhedra are known to be integral (tdi) since 1978, the model has lacked a combinatorial algorithm.
In the lecture, I will give an introduction to the (I think fascinating) model of lattice polyhedra and present some algorithmic results. These results
include a primal-dual (the first combinatorial) algorithm for lattice polyhedra, a reduction of modular ternary lattice polyhedra to submodular flows,
and an iterative rounding algorithm for lattice polyhedra with degree bounds. The latter covers various network design problems with degree bounds such as
degree bounded mincost spanning trees, degree bounded matroids, and degree bounded mincost arborescences.
(Based on joint work with S.Tom McCormick, Satoru Fujishige, Nikhil Bansal, Vish Nagarajan and Jannik Matuschke.)
Colloquium - 16:00
Abstract:
It is well-known as an existence result that every 3-connected graph G=(V,E) on
more than 4 vertices admits a sequence of contractions and a sequence of removal
operations to K_4 such that every intermediate graph is 3-connected. We show
that both sequences can be computed in optimal time, improving the previously
best known running times of O(|V|^2) to O(|E|). This settles also the open
question of finding a linear time 3-connectivity test that is certifying and
extends to a certifying 3-edge-connectivity test in the same time. The
certificates used are easy to verify in time O(|E|).