Monday, November 21, 2011
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136, 10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
The state of the art of the design and analysis of approximation algorithms
for NP-hard discrete optimization has advanced significantly over the past
two decades; furthermore, the most prevalent approach has been to rely on
the strength of natural linear programming relaxations. Work in computational
integer programming over the same time period has shown the power
of adding combinatorially-motivated valid inequalities, but this
has not been employed often in the design of approximation algorithms.
We will show how this approach can be applied in the design and analysis
of primal-dual approximation algorithms. We will present several recent
approximation results along these lines, starting with a (surprisingly
simple) primal-dual analogue of an LP-rounding result of Carr, Fleischer,
Leung, & Phillips for the minimum-cost covering knapsack problem, which
finds a solution of cost at most twice the optimum. We then consider
a number of extensions of this result, and in particular, for the
capacitated lot-sizing problem. Finally, we consider a broad class of
single-machine scheduling problems, where the cost of scheduling each job is
a (job-specific) non-decreasing function of the time at which it completes, and
the objective is to minimize the total cost of the schedule. Bansal and Pruhs
recently gave the first constant approximation algorithm for this setting; we
adapt the primal-dual approach to directly yield a 2-approximation algorithm for
this class of problems.
This is joint work with Tim Carnes and Maurice Cheung.
Colloquium - 16:00
Abstract:
Abstract flows generalize classical network flows by replacing the underlying network by an abstract system of "paths", a family of linearly ordered sets on an arbitrary ground set, fulfilling a simple switching property: Whenever two paths P and Q intersect, there must be another path that only contains elements from the beginning of P and the end of Q. In contrast, flows over time augment the classical network flow model by a notion of time. Here, each edge is equipped with a travel time that specifies the time needed for its traversal.
In the talk, we will discuss abstract flows over time, i.e., a combination of these two concepts. We will illustrate difficulties that arise when travel times are added to the abstract path system, but also show that a maximum abstract flow over time can be obtained by solving a weighted abstract flow problem and constructing a temporally repeated flow from its solution. In the course of the proof, we also show that the relatively modest switching property of abstract path systems already captures many essential properties of classical networks.
This is joint work with Jan-Philipp Kappmeier and Britta Peis.