Monday, November 28, 2011
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett
Lecture - 14:15
Abstract:
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
Abstract:
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.