Monday, December 1, 2014
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Many applications can be formulated as network flow problems with parametric capacities. In many of these applications we would like to find optimal flows for many values of the parameter, or perhaps even the entire curve of parametric values. Unfortunately, in general the number of different optimal solutions contributing to the optimal curve can be exponential.
Consider for now the specialization to parametric max flow/min cut. When the parametric capacities satisfy a "source-sink monotone" property (which is the case in many important applications), then the optimal min cuts are "nested", or "monotone", in the parameter. This immediately implies that there are at most n-1 optimal min cuts in the parametric curve. Furthermore, Gallo, Grigoriadis, and Tarjan (GGT) showed that the entire parametric curve can be computed in the same time as a single run of the Push Relabel max flow algorithm. This GGT result was later extended in several other papers.
There is a general theory by Topkis that includes source-sink monotone max flow min cut as a special case. Consider a function f(X,t) where X belongs to a "lattice", and t is a parameter. Then if f is submodular in X for each t, and if f satisfies a "decreasing differences" property, then there are optimal solutions X^*(t) for each t that are monotone in t.
However, all the examples known until now of Topkis's framework applied to combinatorial optimization concern problems with 0-1 variables. Thus it is natural to wonder if it can be applied to more general problems such as min-cost flow. For this to work we would need a submodularity result. Happily, it turns out that Murota proved such a result: The optimal min-cost flow objective value is submodular in the dual variables, where we consider the dual variables as living on the lattice of integer vectors in \R^N with "meet" being component-wise min, and "join" being component-wise max. With this result in hand we can then show that various parametric min-cost flow problems fit into Topkis's framework and so have monotone optimal dual solutions.
A natural question is whether one can also generalize GGT's algorithmic result. We further show how to adapt Bertsekas's Relax algorithm for min-cost flow into a parametric version that can solve a sequence of parametric problems in the same time as solving a single min-cost flow. This algorithm is mainly of interest when the costs are "small" integers.
(joint work with Britta Peis, Jannik Matuschke, and Gianpaolo Oriolo)
Colloquium - 16:00
Abstract:
In the stable marriage and roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. In this talk we investigate the complexity of finding a solution satisfying additional constraints on restricted pairs of agents. Restricted pairs can be either all forced or all forbidden. In the former case a stable solution must contain all of the forced pairs, while in the latter case none of the forbidden pairs must be contained in a stable solution.
A polynomial-time algorithm is known to decide whether such a solution exists in the presence of restricted edges. If the answer is no, one might look for a solution close to optimal. Since optimality in this context means that the matching is stable and satisfies all constraints on restricted pairs, there are two ways of relaxing the constraints by permitting a solution to: (1) be blocked by some pairs (as few as possible), or (2) violate some constraints on restricted pairs (again as few as possible). We will sketch the complexity of these two problems in general and special cases.