Jansen, Klaus (2012) A Fast Approximation Scheme for the Multiple Knapsack Problem. In: Sofsem 2012: Theory and Practice of Computer Science. ; 7147 , ed. by Friedrich, G., Gottlob, G., Katzenbeisser, S. and Turan, G.. Lecture Notes in Computer Science . Springer-Verlag Berlin, Berlin, pp. 313-324. ISBN 0302-9743978-3-642-27659-0

Full text not available from this repository.

Abstract

In this paper we propose an improved efficient approximation scheme for the multiple knapsack problem (MKP). Given a set A of n items and set B of in bins with possibly different capacities, the goal is to find a subset S subset of A of maximum total profit that can be packed into B without exceeding the capacities of the bins. Chekuri and Khanna presented a PTAS for MKP with arbitrary capacities with running time n(O(1/epsilon 8 log(1/epsilon))). Recently we found an efficient polynomial time approximation scheme (EPTAS) for MKP with running time 2(O(1/epsilon log(1/epsilon))) poly(n). Here we present an improved EPTAS with running time 2(O(1/epsilon log4(1/epsilon))) + poly(n). If the integrality gap between the ILP and LP objective values for bin packing with different sizes is bounded by a constant, the running time can be further improved to 2(O(1/epsilon log2 (1/epsilon))) + poly(n).

Document Type:	Book chapter
Additional Information:	Univ Kiel, Inst Informat, D-24098 Kiel, Germany. Jansen, K (reprint author), Univ Kiel, Inst Informat, Olshaussenstr 40, D-24098 Kiel, Germany. kj@informatik.uni-kiel.de
Research affiliation:	OceanRep > The Future Ocean - Cluster of Excellence
Publisher:	Springer-Verlag Berlin
Projects:	Future Ocean
Date Deposited:	14 May 2014 10:00
Last Modified:	14 May 2014 10:00
URI:	https://oceanrep.geomar.de/id/eprint/24050

Actions (login required)

View Item