Approximation schemes for the subset-sum problem: Survey and experimental analysis
type: Item
instance of: scholarly article
title: Approximation schemes for the subset-sum problem: Survey and experimental analysis
zbMATH Open document ID: 0583.90070
DOI: 10.1016/0377-2217(85)90115-8
author: Silvano Martello
author: Paolo Toth
published in: European Journal of Operational Research
publication date: 1985-01-01T00:00:00Z
review text: Given n positive integers \(w_ 1,\ldots,w_ n\) and a positive integer W the subset-sum problem (SSP) is to find a subset of \(N=\{1,\ldots,n\}\) so as to max\(\sum_{i\in S}w_ i\) s.t. \(\sum_{i\in S}w_ i\leq W\). The best-known heuristics for this problem are approximation schemes based on worst-case analysis (WCA) which establishes the maximum relative error the algorithm can produce. WCA is based on the following definition of worst-case performance ratio r(H): it is the largest number smaller or equal to H(I)/Z(I) for all possible instances I of SSP, Z(I) is the value of optimal solution of problem I, H(I) is the value of the solution found by a heuristic algorithm H when applied to problem I. The polynomial approximation schemes of Johnson, Martello and Toth, fully polynomial approximation schemes of Lawler and Gens and Levner are experimentally examined. The results of computational experiments (the code was written in FORTRAN IV and was run on a CDC Cyber 730) have shown that all the approximate algorithms for SSP have an average performance much better than their worst-case performance. Although polynomial approximation schemes have a worse bound on computing time, their average performance appears superior to that of the fully polynomial approximation schemes. The most effective scheme is that proposed by the authors.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3934775
zbMATH Keywords: subset-sum problem
zbMATH Keywords: heuristics
zbMATH Keywords: polynomial approximation schemes
zbMATH Keywords: computational experiments
reviewed by: Oleg A. Shcherbina
MaRDI profile type: Publication
full work available at URL: 0377-2217(85)90115-8
OpenAlex ID: W2012468431
cites work: Hard Knapsack Problems
cites work: Probabilistic analysis of the subset-sum problem
cites work: Q3888846
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Approximation algorithms for combinatorial problems
cites work: Fast Approximation Algorithms for Knapsack Problems
cites work: Worst-case analysis of greedy algorithms for the subset-sum problem
cites work: A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
description: scientific article; zbMATH DE number 3934775