Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
type: Item
instance of: scholarly article
title: Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
zbMATH Open document ID: 0532.90075
DOI: 10.1016/0377-2217(84)90053-5
author: M. R. B. Clarke
author: Alan Frieze
published in: European Journal of Operational Research
publication date: 1984-01-01T00:00:00Z
review text: This paper is concerned with the m-dimensional 0-1 knapsack problem: \[ (1.1)\quad Maximise\quad z=\sum^{n}_{j=1}c_ jx_ j, \] \[ subject\quad to\quad \sum^{n}_{j=1}a_{ij}x_ j\leq b_ i,\quad 0\leq x_ j\leq 1,\quad x_ j\quad integer,\quad j=1,...,n;\quad i=1,...,m, \] where for all i, j, \(a_{ij}\geq 0\), \(b_ i\), \(c_ j>0\). m is considered to be a fixed constant. The problem is known to be NP- hard even when \(m=1\) and so there is interest in finding heuristics which work in polynomial time (polynomial in the input length) and have a guaranteed accuracy. Given \(\epsilon>0\) we say that an algorithm is an \(\epsilon\)-approximation algorithm if it always produces a solution \(\hat x\) with objective value \(\hat z\) that satisfies \[ (1.2)\quad z^*-\hat z\leq \epsilon z^* \] where \(z^*\) is the maximum value of z in (1.1). The aim of this paper is two-fold. In Section 2 we present a polynomial approximation scheme for problem (1.1), i.e. for each \(\epsilon>0\) we describe an algorithm \(A_{\epsilon}\), which is an \(\epsilon\)- approximation algorithm and runs in time polynomial in the length of the input description of (1.1). In Section 3 we conduct a probabilistic analysis of this problem and obtain reasonable tight bounds for the asymptotic behaviour of the objective value \(z^*\). A simple consequence of this analysis is that with probability \(\to 1\) as \(n\to \infty\) the solution obtained by rounding down the solution to the linear program (1.1) satisfies (1.2) with \(\epsilon =n^{-a}\) provided \(a<1/(m+1)\).
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3845351
zbMATH Keywords: dual simplex algorithm
zbMATH Keywords: epsilon-approximation algorithm
zbMATH Keywords: m-dimensional 0- 1 knapsack problem
zbMATH Keywords: polynomial approximation scheme
zbMATH Keywords: probabilistic analysis
zbMATH Keywords: tight bounds
zbMATH Keywords: asymptotic behaviour
Wikidata QID: Q57401633
MaRDI profile type: Publication
full work available at URL: 0377-2217(84)90053-5
OpenAlex ID: W2055037276
cites work: Q4091421
cites work: Approximate algorithms for some generalized knapsack problems
cites work: Q4065548
cites work: Khachiyan’s algorithm for linear programming
cites work: `` Strong '' NP-Completeness Results
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Approximation algorithms for combinatorial problems
cites work: Q4197641
cites work: Q3912008
cites work: Q4171868
cites work: A Stability Concept For Zero-One Knapsack Problems And Approximation Algorithms
cites work: Approximate Algorithms for the 0/1 Knapsack Problem
cites work: Q5534682
Recommended article: Q5240419
Recommended article: The multidimensional 0-1 knapsack problem -- bounds and computational aspects
Recommended article: Note—An Approximate Algorithm for Multidimensional Zero-One Knapsack Problems—A Parametric Approach
Recommended article: Approximation algorithms on 0--1 linear knapsack problem with a single continuous variable
Recommended article: Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem
Recommended article: A Note on Approximation Schemes for Multidimensional Knapsack Problems
Recommended article: Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem
Recommended article: The fully polynomial approximation algorithm for the 0-1 knapsack problem
Recommended article: Approximation algorithms for knapsack problems with cardinality constraints
Recommended article: Approximation schemes for the parametric knapsack problem
description: scientific article; zbMATH DE number 3845351