Approximation for multi-knapsack problem
type: Item
instance of: scholarly article
title: Approximation for multi-knapsack problem
zbMATH Open document ID: 0862.90107
author: Li'ang Zhang
author: Luyang Li
author: Xiong Huang
published in: Chinese Science Bulletin
publication date: 1997-05-25T00:00:00Z
review text: The multi-knapsack problem is defined as follows: For given \(n\) items and \(k\) knapsacks, there is a weight \(w_j\) and a value \(v_j\) for item \(j\) \((1\leq j\leq n)\), and a weight constraint \(B_i\) for knapsack \(i\) \((1\leq i\leq k)\), where \(w_j\), \(v_j\), \(B_i>0\). The object is to maximize the total value of all items packed in knapsacks subject to the constraint that the total weight of all items in each of the knapsacks does not exceed its weight constraint. When \(k\) is a fixed positive integer, the problem is called the \(k\)-knapsack problem. Especially, the 1-knapsack problem is just the ordinary \(0/1\) knapsack problem and has an FPTAS. We proved that for every fixed \(k\geq 2\), \(k\)-knapsack has a PTAS and a pseudo-polynomial time algorithm, but has no FPTAS unless \(P=NP\). In this note, we prove that if \(P\neq NP\), the multi-knapsack problem has no polynomial-time approximation algorithm \(A\) with \(R_A\leq {6\over 5}\). This remains true even if all knapsacks have the same weight constraints and every item's weight is equal to its value, i.e. \(B_i=B\) \((1\leq i\leq k)\) and \(w_j=v_j\) \((1\leq j\leq n)\). According to this theorem, the multi-knapsack problem has no PTAS. Moreover, we give a polynomial-time approximation algorithm with performance ratio 2 for the multi-knapsack problem.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 940609
zbMATH Keywords: multi-knapsack problem
zbMATH Keywords: pseudo-polynomial time algorithm
zbMATH Keywords: polynomial-time approximation algorithm
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 940609