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

この論文にアクセスする

この論文をさがす

著者

抄録

<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>

収録刊行物

  • 日本オペレーションズ・リサーチ学会論文誌

    日本オペレーションズ・リサーチ学会論文誌 60(1), 15-23, 2017

    公益社団法人 日本オペレーションズ・リサーチ学会

各種コード

  • NII論文ID(NAID)
    130005316101
  • NII書誌ID(NCID)
    AA00703935
  • 本文言語コード
    ENG
  • ISSN
    0453-4514
  • NDL 記事登録ID
    027850675
  • NDL 請求記号
    Z53-M226
  • データ提供元
    NDL  J-STAGE 
ページトップへ