Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, November 28, 2011

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin

Lecture - 14:15

Klaus Jansen - Christian-Albrechts-Universität zu Kiel

Approximation algorithms for a knapsack and related scheduling problem

In the first part of the talk we study the multiple knapsack problem (MKP); a well-known generalization of the classical knapsack problem. Given a set A of n items and set B of m bins with possibly different capacities, the goal is to find a subset S of A of maximum total profit that can be packed into B without exceeding the capacities of the bins. The decision version of MKP is strongly NP-complete, since it is a generalization of the bin packing problem.Furthermore, MKP does not admit a fully polynomial time approximation scheme (FPTAS) even if the number m of bins is two. Kellerer gave a polynomial time approximation scheme (PTAS) for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with general capacities with running time n^{O(1/epsilon^8 log(1/epsilon))}. In this talk we propose an efficient PTAS (EPTAS) with parameterized running time T_{MKP}(n,epsilon) = 2^{O(1/epsilon log^4(1/epsilon))} + poly(n) for MKP. This also solves an open question by Chekuri and Khanna. If the modified round-up property for bin packing with different bin sizes is true, the running time can be further improved to T_{MKP}(n,epsilon) = 2^{O(1/epsilon log^2(1/epsilon))} + poly(n). In the second part (joint work with F. Diedrich, L. Prädel, U. Schwarz, and O. Svensson) we consider a parallel machine scheduling problem. In this problem some jobs are already fixed in the system or intervals of non-availability of some machines must be taken into account. The first problem occurs when high-priority jobs are already scheduled in the system while the latter problem is due to regular maintenance of machines. Formally, an instance consists of m machines and n jobs with processing times p_1,...,p_n. The first k jobs are fixed via a list (m_1,s_1), ... , (m_k,s_k) given a machine and starting time for each fixed job. The objective is to assign the other n-k jobs non-preemptively and without overlapping to the machines while minimizing the maximum completion time (the makespan) among all jobs. Scharbrodt, Steger, and Weisser proved that there is no approximation algorithm for this scheduling problem with ratio strictly better than 3/2, unless P=NP. Furthermore, they proposed an approximation algorithm with ratio 2+epsilon for this problem. In this talk we present an approximation algorithm for the scheduling problem with ratio 3/2, closing the gap between the best known upper and lower bound. The running time of our algorithm can be bounded by O(n log n + log((n/m) max_j p_j) (n + T_{MKP}(n,1/8))), where T_{MKP}(n,1/8) is the running time of an approximation algorithm for the multiple knapsack problem (MKP) with accuracy epsilon = 1/8.

Colloquium - 16:00

Christian Stump - Berlin

A new approach to cluster complexes of finite types and of generalized associahedra

I will present a new combinatorial approach to understand the combinatorics and geometry of cluster complexes of finite types. This approach uses a new description of cluster complexes by the author together with C. Ceballos and J.-P. Labbé which describes cluster complexes in terms of subword complexes introduced by Knutson and Miller in the context of Schubert varieties. Based on work by V. Pilaud and F. Santos, this yields a new construction of the polytopal realization of the polar dual of cluster complexes which turns out to isomorphic to the two known constructions by F. Chapoton, S. Fomin, and A. Zelevinsky and by C. Hohlweg, C. Lange, and H. Thomas. Its advantage is that we are able to give a vertex description, and a natural Minkowski decomposition.
I will keep the presentation as accessible as possible by focusing on the construction for the symmetric group, while I will only hint the interested listener to the general type-free construction.
The talk is based on two joint papers with C. Ceballos, J.-P. Labbé and with V. Pilaud.

Letzte Aktualisierung: 16.11.2011