Horst Hamacher - TU Kaiserslautern

Decomposition of integer into consecutive-1 matrices and applications

Any integer matrix A can be decomposed into a non-negative linear combination of (0,1) matrices with the consecutive-1 property (either in rows or in columns). In this talk we will review results on how to do this decomposition with various objectives to be minimized such as
- sum of coefficients
- number of consecutive-1 matrices to be used
Moreover a sequencing problem of the consecutive-1 matrices is considered. As applications we discuss the modulation of radiation in cancer therapy, the design of stops in public transportation systems, and the solution of integer programs via (semi-) simultaneous network flows.
The presentation will be based on joint work with Ravi Ahuja, Davaatseren Baatar, Natshia Boland, Alexander Engau, Frank Lenzen, Annegret Liebers, Anita Schöbel and Dorothea Wagner.

Colloquium - 16:00

Heiko Schilling - TU Berlin

Length-Bounded Cuts and Flows

Abstract: An L-length-bounded cut in a graph G with source s, and sink t is a cut that destroys all s-t-paths of length at most L. An L-length-bounded flow is a flow in which only flow paths of length at most L are used. The first research on path related constraints we are aware of was done in 1978 by Lovasz, Neumann Lara, and Plummer. Among others they show that the minimum length-bounded node-cut problem is polynomial for L<=4. We show that the minimum length-bounded cut problem turns out to be NP-hard to approximate within a factor of at least 1.1377 for L>=5 in the case of node-cuts and for L>=4 in the case of edge-cuts (both in graphs with unit edge lengths). We also give approximation algorithms of ratio min(L,n/L) in the node case and min(L,n^2/L^2,\sqrt{m}) in the edge case, where n denotes the number of nodes and m denotes the number of edges. For classes of graphs such as constant degree expanders, hypercubes, and butterflies, we obtain $O(log n)-approximations by using the Shortening Lemma for flow numbers [Kolman and Scheideler, SODA'02]. We discuss the integrality gaps of the LP relaxations of length-bounded flow and cut problems, which can be of size Omega(\sqrt{n}). We show that edge- and path-flows are not polynomially equivalent for length-bounded flows, analyze the structure of optimal solutions and give instances where each maximum flow ships a large percentage of the flow along paths with an arbitrarily small flow value.

This is joint work with Georg Baier, Thomas Erlebach, Alex Hall, Ekki Köhler, and Martin Skutella and will be presented on the 33rd International Colloquium on Automata, Languages, and Programming (ICALP) this year.