Monday, October 27, 2007
Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
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
Abstract:
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.