An approximation algorithm for the covering 0-1 integer program (The state-of-the-art optimization technique and future development)

Abstract

The covering 0-1 integer program is a generalization of fundamental combinatorial optimization problems such as the vertex cover problem, the set cover problem, and the minimum knapsack problem. In this article, extending a 2-approximation algorithm for the minimum knapsack problem by Carnes and Shmoys (2015), we propose a triangle_{2^{-}} approximation algorithm, where $Delta$_{2} is the second largest number of non-zero coefficients in the constraints.