Affordable Access

Publisher Website

Approximation schemes for the subset-sum problem: Survey and experimental analysis

Authors
Journal
European Journal of Operational Research
0377-2217
Publisher
Elsevier
Publication Date
Volume
22
Issue
1
Identifiers
DOI: 10.1016/0377-2217(85)90115-8
Keywords
  • Integer Programming
  • Heuristics
  • Computational Analysis

Abstract

Abstract Given a set of n positive integers w 1,…, w n and a positive integer W, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding, W. The most important heuristics for this problem are approximation schemes based on a worst-case analysis. We survey them and experimentally analyze their statistical behaviour on a large number of test problems.

There are no comments yet on this publication. Be the first to share your thoughts.