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

Access this Article

Search this Article

Author(s)

Abstract

<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

  • Journal of the Operations Research Society of Japan

    Journal of the Operations Research Society of Japan 60(1), 15-23, 2017

    The Operations Research Society of Japan

Codes

  • NII Article ID (NAID)
    130005316101
  • NII NACSIS-CAT ID (NCID)
    AA00703935
  • Text Lang
    ENG
  • ISSN
    0453-4514
  • NDL Article ID
    027850675
  • NDL Call No.
    Z53-M226
  • Data Source
    NDL  J-STAGE 
Page Top