logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Two linear approximation algorithms for the subset-sum problem

delete2000-01-01
delete11
PRE
AI
H
Hans Kellerer *
R
Renata Mansini
M
M. Grazia Speranza
DOI：10.1016/S0377-2217(99)00157-5delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
In this paper we study the subset-sum problem (SSP), which is the problem of finding, given a set of n positive integers and a knapsack of capacity c, a subset the sum of which is closest to c without exceeding the value c. A short algorithm with worst-case guarantee 3/4 is introduced which outperforms Martello and Toth's 3/4 algorithm requiring a complexity time of O(n) instead of O(n(2)). The second linear time algorithm reaches a 4/5 worst-case performance ratio. Both bounds are shown to be tight. Computational results on randomly generated and deterministic test problems are reported. (C) 2000 Published by Elsevier Science B.V. All rights reserved.
Keywords:
subset-sum
approximation algorithms
worst-case performance
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

European Journal of Operational Research cover
European Journal of Operational Research
IF:
6
Papers:
2.2W
Citations:
6.4W

Organization

No organization information available