Departmental Bulletin Paper On E-kKP as a knapsack problem related to the conventional 2-approximation algorithm for the 0-1 knapsack problem

Iida, Hiroshi

66 ( 1 )  , pp.197 - 205 , 2015-07-25 , 小樽商科大学
ISSN:04748638
NCID:AN00114062
Description
論説
This piece picks up E-kKP as a knapsack problem in relation to the conventional and the simplest 2-approximation algorithm for the 0-1 knapsack problem. Taking account of the similarity between E-kKP and the multiple-choice knapsack problem, we mention how to produce two candidates onto the conventional and also how to obtain an optimal solution of LP-relaxed E-kKP that we require so as to produce the two candidates.
Full-Text

https://barrel.repo.nii.ac.jp/?action=repository_action_common_download&item_id=184&item_no=1&attribute_id=19&file_no=1

Number of accesses :  

Other information