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 17, 2011

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041

Lecture - 14:15

Britta Peis - Otto-von-Guericke-Universitšt Magdeburg

Integer linear programs with submodular structure

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

Jens Schmidt - Freie Universitšt Berlin

Structure and Constructions of 3-Connected Graphs

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|).

Letzte Aktualisierung: 14.01.2011