Parameterized approximation scheme for the multiple knapsack problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parameterized approximation scheme for the multiple knapsack problem

Full text

Pdf (433 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 665-674

Year of Publication: 2009

Author

Klaus Jansen

Universität zu Kiel, Kiel, Germany

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 105, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

The multiple knapsack problem (MKP) is a well-known generalization of the classical knapsack problem. We are given a set A of n items and set B of m bins (knapsacks) such that each item a ∈ A has a size size(a) and a profit value profit(a), and each bin b ∈ B has a capacity c(b). The goal is to find a subset U ⊂ A of maximum total profit such that U can be packed into B without exceeding the capacities. The decision version of MKP is strongly NP-complete, since it is a generalization of the classical knapsack and bin packing problem. Furthermore, MKP does not admit an FPTAS even if the number m of bins is two. Kellerer gave a PTAS for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with general capacities with running time n^{O(log(1/ε)/ε}⁸). In this paper we propose an EPTAS with parameterized running time 2^{O(log(1/ε)/ε}⁵) · poly(n) + O(m) for MKP. This solves also an open question by Chekuri and Khanna.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E. Balas and E. Zemel: An algorithm for large zero-one knapsack problems, Operations Research, 28 (1980), 1130--1154.
	2	M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan: Time bounds for selection, Journal of Computer and System Sciences, 7 (1973), 448--461.
	3	Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
	4	Chandra Chekuri , Sanjeev Khanna, A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem, SIAM Journal on Computing, v.35 n.3, p.713-728, 2005 [doi>10.1137/S0097539700382820]
	5	F. Diedrich, K. Jansen, F. Pascual, and D. Trystram: Approximation algorithms for scheduling wit reservations, Proceedings of Conference on High Performance Computing, HiPC 2007, 297--307.
	6	Dorit Dor , Uri Zwick, Selecting the Median, SIAM Journal on Computing, v.28 n.5, p.1722-1758, April/May 1999 [doi>10.1137/S0097539795288611]
	7	R. Downey: Parametrized complexity for the skeptic, Proceedings of IEEE Conference on Computational Complexity, CCC 2003, 147--169.
	8	M. R. Fellows: Blow-ups, win/win's, and crown rules: some new directions in FPT, Proceedings of Workshop on Graph Theoretical Concepts in Computer Science, WG 2003, LNCS 2880, 1--12.
	9	M. D. Grigoriadis , L. G. Khachiyan , L. Porkolab , J. Villavicencio, Approximate Max-Min Resource Sharing for Structured Concave Optimization, SIAM Journal on Optimization, v.11 n.4, p.1081-1091, 2000 [doi>10.1137/S1052623499358689]
	10	C. Kenyon and E. Remila: Approximate strip packing, Mathematics of Operations Research, 25 (2000), 645--656.
	11	Hans Kellerer, A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.51-62, August 08-11, 1999
	12	H. Kellerer, U. Pferschy, and D. Pisinger: Knapsack Problems, Springer Verlag, Berlin, 2004.
	13	E. L. Lawler: Fast approximation algorithms for knapsack problems, Mathematics of Operations Research, 4 (1979), 339--356.
	14	J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, February 1990 [doi>10.1007/BF01585745]
	15	Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
	16	D. Marx: Parametrized complexity and approximation algorithms, The Computer Journal, 51 (2008), 60--78.
	17	Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
	18	Mark Scharbrodt , Angelika Steger , Horst Weisser, Approximability of scheduling with fixed jobs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.961-962, January 17-19, 1999, Baltimore, Maryland, United States
	19	David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]