covering integer program

An improved approximation algorithm for the covering 0-1 integer program

  • Tomonari Kitahara
  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories Approximation Algorithms Tags , ,

    We present an improved approximation algorithm for the covering 0-1 integer program (CIP), a well-known problem as a natural generalization of the set cover problem. Our algorithm uses a primal-dual algorithm for CIP by Fujito (2004) as a subroutine and achieves an approximation ratio of (f- (f-1)/m) when m is greater than or equal to … Read more

    A 2-approximation algorithm for the minimum knapsack problem with a forcing graph

  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories Approximation Algorithms Tags , , ,

    Carnes and Shmoys (2015) 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 … Read more