Institutt for informatikk


There has not been added a translated version of this content. You can either try searching or go to the "area" home page to see if you can find the information there

Approximation algorithms for a scheduling and related knapsack problem

Speaker: Klaus Jansen, University Kiel.

Abstract: In the first part of the talk we consider a parallel machine scheduling problem where some jobs are already fixed in the system or intervals of non-availability of some machines must be taken into account. 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/epsilon)), where T_{MKP}(n,1/epsilon) is the running time of an approximation algorithm for the multiple knapsack problem (MKP) with fixed accuracy epsilon = 1/8. In the second part 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 improved 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).

NB: Refreshments will be served in the lobby before the seminar.