Approximation Algorithms for the Generalized Multiple Knapsack Problems with K Restricted Elements
Authors:
- Binchao HuangBHBinchao Huang
- Jianping LiJLJianping Li
- Ko-Wei LihKLKo-Wei Lih
- Haiyan WangHWHaiyan Wang
- 1 August 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 470-474
Abstract
We are given a set of items, and a set of knapsacks. Both the weight and the profit of an item are functions of the knapsack, and each knapsack has a positive real capacity. A restriction is setting that the number of the items which are admissible to each knapsack is no more than k, and these items are taken as input for each knapsack. We consider two following objectives: (1) maximizing the total profit of all the knapsacks (Max-Sum k-GMK), (2) maximizing the minimum profit of all the knapsacks (Max-Min k-GMK). We show that the two problems are NP-complete when k is greater than or equal to 4. For the Max-Sum k-GMK problem, we can obtain a 1/2-approximation algorithm, and especially when k=2, we design an optimal algorithm. For the Max-Min k-GMK problem, we present a 1/ (k-1)-approximation algorithm, and especially when k=2, this algorithm is an optimal algorithm.Keywords
This publication has 7 references indexed in Scilit:
- Knapsack Problems2004
- Approximation Algorithms2003
- Approximation Algorithms for the Multiple Knapsack Problem with Assignment RestrictionsJournal of Combinatorial Optimization, 2000
- The Multiple Subset Sum ProblemSIAM Journal on Optimization, 2000
- Solving Multiple Knapsack Problems by Cutting PlanesSIAM Journal on Optimization, 1996
- An approximation algorithm for the generalized assignment problemMathematical Programming, 1993
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991