Network Flow Problems in Additive Networks

Speaker :       Prof. Dr. Franz J. Brandenburg
                University of Passau, Germany

Title:          Network Flow Problems in Additive Networks

Date:           Monday, 15 March 2004

Time:           4:00 pm - 5:00 pm

Venue:          Lecture Theatre F (Leung Yat Seng Lecture Theatre) 
                (near lift nos. 25/26)   

ABSTRACT:

We introduce networks with additive losses and gains in which each arc has 
a gain function g_a. If a positive flow x enters an arc, then x+g(a) units 
exit. Arcs may increase or consume flow, i.e., they are gainy or lossy.
Such networks have various applications, e.g., in data communication, 
transportation and financial analysis.

In this talk we investigate the maximum flow and the minimum cost flow 
problems. We show that the maximum low problem is strongly NP-hard, even 
in unit gain networks. It remains NP-hard, if all arcs are lossy. However, 
it becomes solvable in O(nm^2) time in unit loss networks. For the minimum 
cost flow problem we extend the successive shortest path algorithm from 
standard to unit loss networks with almost the same running times.

Our NP-results sharply contrast efficient polynomial time solutions of
flow problems in generalized networks with multiplicative losses and gains.
Algorithmically, additive networks are harder than multiplicative networks.

*******************
Biography:

Prof. Dr. Franz J. Brandenburg received his Diplom in mathematics at 
the University of Bonn, Germany, in 1973. A PhD in computer science 
followed in 1978 and a habilitation, also in computer science, in 1982. 
He held postdoc and visiting professor positions at UC Santa Barbara, 
Univ. of Braunschweig, Germany, and Univ. of Dortmund, Germany, before 
becoming a full professor of computer science at the Univ. of Passau, 
Germany, in 1983. From 1992-1994 he served there as Dean of the Faculty 
of Mathematics and Computer Science. Since 1999 he has been the Dean of 
Studies. From 1991-1995 he served as Chairman of the National German 
Board of Computer Science Faculties (Fakult"atentag Informatik). His 
research interests include algorithms, graph drawing, computational 
geometry, formal languages, automata theory, complexity theory, and 
computer science in education. He has over 60 publications in scientific 
journals and conference proceedings. Among others, he organized STACS 
1987 in Passau, Graph Drawing 1995 in Passau, and in 2003 the Joint 
Chinese-German Workshop on Theoretical Computer Science in Shanghai.