最新号は「2016-1: Yotaro TAKAZAWA and Shinji MIZUNO. A 2-approximation algorithm for the minimum knapsack problem with a forcing graph」です。
Carnes and Shmoys  presented a 2-approximation algorithm for the minimum knapsack problem. We extend their algorithm to the minimum knapsack problem with a forcing graph (MKPFG), which has a forcing constraint for each edge in the graph. The forcing con-straint means that at least one item (vertex) of the edge must be packed in the knapsack. The problem is strongly NP-hard, since it includes the vertex cover problem as a special case. Generalizing the proposed algorithm, we also present an approximation algorithm for the covering integer program with 0-1 variables.