Industrial Engineering and Economics News

"Department of Industrial Engineering and Economics Working Paper" is now available for viewing

  • RSS

July 05, 2016

Department of Industrial Engineering and Economics Working Paper

Department of Industrial Engineering and Economics Working Paper

Department of Industrial Engineering and Economics started to issue Working Paper series, which reports recent outcomes of our research, in Publication section of this web site. The latest issue is 2016-1: Yotaro TAKAZAWA and Shinji MIZUNO. A 2-approximation algorithm for the minimum knapsack problem with a forcing graph.

Abstract

Carnes and Shmoys [2] 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.

Following issues of Working Paper will appear as soon as available.

  • RSS

Page Top

CLOSE

CLOSE