A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH

DOI Web Site Web Site 12 References

Search this article

Description

<p>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 constraint 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.</p>

Journal

References(12)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top