Abstract
This paper considers two variants of Multiple Knapsack Problems. The first one is the Multiple Knapsack Problem with Assignment Restrictions and Capacity Constraints (MK-AR-CC). In the MK-AR-CC(\(k\)) (where \(k\) is a positive integer), a subset of knapsacks is associated with each item and the item can be packed into only those knapsacks (Assignment Restrictions). Furthermore, the size of each knapsack is at least \(k\) times the largest item assignable to the knapsack (Capacity Constraints). The MK-AR-CC(\(k\)) is NP-hard for any constant \(k\). In this paper, we give a polynomial-time \(\left( 1+\frac{2}{k+1}+\epsilon \right) \)-approximation algorithm for the MK-AR-CC(\(k\)), and give a lower bound on the approximation ratio of our algorithm by showing an integrality gap of \(\left( 1+\frac{1}{k}-\epsilon \right) \) for the IP formulation we use in our algorithm, where \(\epsilon \) is an arbitrary small positive constant. The second problem is the Splittable Multiple Knapsack Problem with Assignment Restrictions (S-MK-AR), in which the size of items may exceed the capacity of knapsacks and items can be split and packed into multiple knapsacks. We show that approximating the S-MK-AR with the ratio of \(n^{1-\epsilon }\) is NP-hard even when all the items have the same profit, where \(n\) is the number of items and \(\epsilon \) is an arbitrary positive constant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aerts, J., Korst, J., Spieksma, F.: Approximation of a retrieval problem for parallel disks. In: Proceedings of the 5th Italian Conference on Algorithms and Complexity (CIAC), pp. 178–188 (2003)
Aerts, J., Korst, J., Spieksma, F., Verhaegh, W., Woeginger, G.: Random redundant storage in disk arrays: complexity of retrieval problems. IEEE Transactions on Computers 52(9), 1210–1214 (2003)
Cohen, R., Katzir, L., Raz, D.: An efficient approximation for the generalized assignment problem. Information Processing Letters 100(4), 162–166 (2006)
Dawande, M., Kalagnanam, J., Keskinocak, P., Salman, F.S., Ravi, R.: Approximation algorithms for the multiple knapsack problem with assignment restrictions. Journal of Combinatorial Optimization 4(2), 171–186 (2000)
Feige, U., Vondrak, J.: Approximation algorithms for allocation problems: improving the factor of \(1-1/e\). In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 667–676 (2006)
Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum separable assignment problems. Mathematics of Operations Research 36(3), 416–431 (2011)
Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pp. 302–311 (1984)
Kellerer, H., Pferschy, U.: A new fully polynomial time approximation scheme for the knapsack problem. Journal of Combinatorial Optimization 3(1), 59–71 (1999)
Kuhn, H.W.: The hungarian method for the assignment problem. Naval Research Logistics Quarterly 2(1–2), 83–97 (1955)
Magazine, M.J., Oguz, O.: A fully polynomial approximation algorithm for the 0–1 knapsack problem. European Journal of Operational Research 8(3), 270–273 (1981)
Murty, K.G.: Network Programming. Prentice-Hall, Inc (1992)
Nutov, Z., Beniaminy, I., Yuster, R.: A (\(1-1/e\))-approximation algorithm for the generalized assignment problem. Operations Research Letters 34(3), 283–288 (2006)
Sakai, K., Okabe, Y.: Quality-aware energy routing toward on-demand home energy networking. In: Proceeding of the 2011 IEEE Consumer Communications and Networking Conference (CCNC), pp. 1041–1044 (2011)
Shmoys, D.B., Tardos, É.: An approximation algorithm for the generalized assignment problem. Mathematical Programming 62(1–3), 461–474 (1993)
Takuno, T., Kitamori, Y., Takahashi, R., Hikihara, T.: AC power routing system in home based on demand and supply utilizing distributed power sources. Energies 4(5), 717–726 (2011)
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 681–690 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Miyazaki, S., Morimoto, N., Okabe, Y. (2015). Approximability of Two Variants of Multiple Knapsack Problems. In: Paschos, V., Widmayer, P. (eds) Algorithms and Complexity. CIAC 2015. Lecture Notes in Computer Science(), vol 9079. Springer, Cham. https://doi.org/10.1007/978-3-319-18173-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-18173-8_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18172-1
Online ISBN: 978-3-319-18173-8
eBook Packages: Computer ScienceComputer Science (R0)