Monday, October 27, 2007
Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
Lecture - 14:15
We consider the min cut problem when capacities depend on a parameter $\lam$. There are some classes of this parametric min cut problem that are known to have the nice structural property that min cuts are nested in $\lam$, and the nice algorithmic property that all min cuts can be computed in the same asymptotic time as a single min cut computation. We extend these results in several directions: we find three much more general classes of problems for which these two nice properties continue to hold, and we extend other results with the same flavor as well.
Colloquium - 16:00
Given a directed acyclic graph with sources and sinks, consider the set of flows induced by putting non-negative flows on all source-sink paths. The flow through a node is the sum of the flows on all paths containing it. When the number of paths is much larger than the number of nodes, it is more convenient to consider the set of node flows in place of that of path flows. In a make-to-order production planning problem considered by Ball et al.\ (2003), nodes represent components and paths represent product configurations. The linear inequalities defining the set of node flows can then be used to model material compatibility constraints. Ball et al.\ found characterizations of the set of node flows for some special cases. We extend this work in various directions: we allow arbitrary directed networks, we allow both upper and lower bounds on flows, we characterize which valid inequalities are facets, we give fast algorithms for separation, validity, and dimension, and we put all the pieces together into an algorithm for separating to a facet. All algorithms are very efficient, as they are based on max flow and min-cost flow subroutines.