[home] - [up]


Lectures and Colloquia during the semester



April 28, 2003

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 042           - map -
Lecture - 14:15

Bernd Sturmfels- University of California

Computing the Integer Programming Gap

Abstract: We determine the maximal gap between the optimal values of an integer program and its linear programming relaxation, where the matrix and cost function are fixed but the right hand side is unspecified. Our formula involves irreducible decomposition of monomial ideals. The gap can be computed in polynomial time when the dimension is fixed. (Joint work with Serkan Hosten, math.OC/0301266)


Colloquium - 16:00

Thomas Erlebach -ETH Zürich

Algorithmic Problems in Internet Graphs

Abstract: The Internet is a complex network resulting from distributed growth without central control. The structure of this network, viewed on the level of autonomous systems (subnetworks under separate administrative control), is usually represented as a graph whose edges can be classified according to economic relationships. In this talk, we discuss properties of these Internet graphs, describe algorithmic problems that are encountered in their investigation, and present approximation algorithms for some of these problems. In particular, we give a 2-approximation algorithm for a new NP-hard min-cut problem arising in this context.

Parts of the talk are based on joint work with Alexander Hall, Polly Huang, Thomas Schank, and Danica Vukadinovic.


[home] - [up] - [top]