Monday, January 19, 2009
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041
Lecture - 14:15
Abstract:
Submodular set functions are widely used in the economics, operations research, and computer science literature to represent consumer valuations, because they capture the notion of decreasing marginal utilities (or alternatively, economies of scale in a cost framework). Submodular functions also arise as a natural structural form in many classic discrete optimization problems, such as the max-sat problem in Boolean logic, the max-cut problem in networks, or the max-coverage problem in location analysis. In fact, the role of submodularity in discrete optimization is often compared to that of convex functions in continuous optimization. In particular, minimization is "easy," and the past nine years have witnessed a stream of ever faster and simpler algorithms. However, an argument could be made that submodular function maximization is even more important, at least as far as practical applications are concerned.
In this talk, we present submodular function maximization as a unifying framework through which many recent applications may be viewed, and we show that extensions of the classic greedy algorithm may lead to the best-known theoretical performance guarantees in solving these NP-hard problems.
Colloquium - 16:00
Abstract:
We present new results for no-wait flowshop scheduling with respect to machine idle times. In this setting we consider a multistage plant which consists of several identical machines on each stage. All jobs have to be processed in identical stage order without waiting time between consecutive machine stages. Motivated by a problem from steel production, we seek to minimize the number of idle-times on machines of the last stage.
So far, we had shown that this problem is inapproximable for a large class of machine arrangements, leaving open the complexity of the special case with only one machine per stage. Now, we can show that this problem can be solved optimally for two stages, whereas it is inapproximable for three and more stages. In particular, this new result implies inapproximability in a stronger sense and extends the problem class for which we can show inapproximability. The results are based on transformations to what we call the 2- and 3-dimensional Eulerian Extension Problem in a directed graph.
This is joint work with Tobias Jacobs (Albert-Ludwigs-Universität, Freiburg) and Nicole Megow (MPII, Saarbrücken).