Open AccessWorst-Case performance of the successive approximation algorithm for four identical knapsacks
Author(s) -
Zhenbo Wang
Publication year - 2012
Publication title -
journal of industrial and management optimization
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.325
H-Index - 32
eISSN - 1553-166X
pISSN - 1547-5816
DOI - 10.3934/jimo.2012.8.651
Subject(s) - knapsack problem , computer science , algorithm , approximation algorithm
This paper studies the worst-case performance of the successive approximation algorithm for four identical knapsacks. The algorithm packs the knapsacks successively by using an exact algorithm on the remaining items for each single knapsack. We show that it is an 8/11-approximation algorithm, and the bound is tight.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom