Monday, May 23, 2011
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Submodular-function maximization is a central unifying model in
combinatorial optimization.
Applications range from practical problems such as reconfiguring an
environmental
monitoring network, to more stylized problems such as the graph max-cut
problem.
I will describe some of the motivating applications, survey some different
methodologies
for maximizing a submodular function subject to side constraints, and
describe
computational results on environmental-monitoring problem instances for
some of the more
practical algorithms. Interestingly, while some of the algorithms are
aimed at practical
computation via an Operations Research / Mathematical Optimization
approach, and others
are driven by the Computer Science theory of approximation algorithms,
there is significant
common ground.
Colloquium - 16:00
Abstract:
For a set of n points in the plane, the Oja Depth of a point x is the sum of the areas of all triangles defined by x and two points from P,
normalized by the area of convex hull of P. The Oja Depth of P is the minimum Oja Depth of any point in R^2.
The Oja Depth Conjecture states that any set P of n points in the plane has depth at most (n^2)/9. This would be optimal as there are examples where it is not possible to do better. In this talk, we present a proof of this conjecture. In particular, we show that the center of mass of the convex hull has at most the desired depth.
We also sketch an improvement for the higher dimensional case via a different, more combinatorial method.
(Joint work with Nabil H. Mustafa and Hans Raj Tiwary)