[home] - [up]


Lectures and Colloquia during the semester



May 5, 2003

Konrad-Zuse-Zentrum für InformationstechnikBerlin
Takustraße 7, 14195 Berlin
Room 2005 (lecture hall), ground floor

          - map -


Lecture - 14:15

Martin Grötschel -Konrad-Zuse-Zentrum für Informationstechnik

Cardinality homogeneous set systems

Abstract: A subset C of the power set of a finite set E is called cardinality homogeneous if, whenever C contains some set F, C contains all subsets of E of cardinality |F|. Examples of such set systems C are the sets of all even or of all odd cardinality subsets of E, or, for each uniform matroid, its set of circuits and its set of cycles. With each cardinality homogeneous set system C, we associate the polytope P(C), the convex hull of the incidence vectors of all sets in C. We provide a complete and nonredundant linear description of P(C). This system of equations and inequalities is, in general, of exponential size and dense (i.e., almost all coefficients are non-zero). We show that a greedy algorithm optimizes any linear function over P(C), construct, by a dual greedy procedure, an explicit optimum solution of the dual linear program. The dual solution is almost always fractional - even if the objective function is integral. We also describe a polynomial time separation algorithm for the class of polytopes of type P(C).


Colloquium - 16:00

Katharina Langkau -Technische Universität Berlin

New Approximation Results for Flow-Dependent Transit Times

Abstract: Ford and Fulkerson introduced dynamic network flows in the late 1950's as an extension to traditional network flows. In this model, every arc has a certain transit time which specifies the amount of time needed to traverse an arc. Moreover, in contrast to static flow problems, flow values on arcs may change over time.

A very simple class of dynamic flows are the so-called temporally repeated flows. Such flows have the property that they can be compactly encoded as a path decomposition of a static flow. Temporally repeated flows are a powerful tool in solving dynamic flow problems. For instance, Ford and Fulkerson could show that this simple class of flows contains a dynamic s-t-flow of maximum value.

A different approach for solving dynamic flow problems are time-expanded networks. The latter arise from the original network essentially by duplicating the original network for every point in time. The drawback of this approach is that the size of the resulting network is exponential in the input size of the problem. Fleischer and Skutella consider condensed time-expanded networks and present approximation schemes for various dynamic flow problems.

In this talk, I will give a brief introduction to both solution methods; the temporally repeated flows and the condensed time-expanded networks. In particular, we will show how both techniques can be applied to a flow model in which arc transit times are not fixed but may depend on the current flow situation. The latter feature is crucial for various real-life applications, yet, it dramatically increases the degree of difficulty of the resulting optimization problems. In this setting, we will investigate the multi-commodity flow problem. I will present the ideas of a constant approximation algorithm based on temporally repeated flows and an FPTAS based on condensed time-expanded graphs.


[home] - [up] - [top]