This turns out to be a difficult discrete problem (strongly NP-hard). We show how to formulate it in terms of network flow theory. We obtain a bidirected flow problem on an undirected graph G with upper and lower capacities on the edges and some additional node balance conditions. The problem is then reduced to finding a feasible flow in that graph that satisfies all these constraints. In our talk, we introduce a generic algorithm and discuss the encouraging results of a first implementation.
The talk should be accessible to both graduate students and undergraduates; I will provide necessary background information.
This is joint work with Matthias Muller-Hannemann (Berlin) and Karsten Weihe (Konstanz).
Tea. High tea will be served at 3:30pm in the Lounge.
Emmy's. Certain refreshments will be available at the Emmy's after the talk.