Jonsson and Thapper’s paper deals with integer problems that are constrained by positive right-hand sides and that seek to minimize an objective function. Such problems can be approximated so they are easier to solve.
The authors of this paper write that “the approximability of the integer program (IP) has been extensively studied in the case when A is restricted to nonnegative entries. Among the problems described by such programs, one finds the minimum knapsack problem, minimum vertex cover, and various network design problems.” This is an example of the wide range of applications that can be studied under this perspective.
The first section of the paper begins with an introduction that establishes the integer program to be studied, mentions some previous work, and gives the reader a general idea of the current state of research. Section 2 presents the assumption of an unbounded domain through some propositions and lemmas. Section 3 is devoted to treating a bounded domain, including the mathematical background of propositions. Finally, section 4 presents future work. In this section, the authors mention that a tight approximation is obtained, but considering a particular parameterization of the constraint matrix A. They also refer to the work of Hochbaum et al. [1], who developed an algorithm for arbitrary right sides when variables are bounded. According to the authors, “The value of the final solution can then easily be seen to be off by at most, a factor of 2. To use a similar approach, one would like to prove that polynomial time solvability is retained for monotone inequalities, when arbitrary right-hand sides and bounded domain is substituted with positive right-hand sides and unbounded domain.”
Such programs have been studied before, but from a different perspective. This paper makes an important contribution to the field, as the approximation can be used for these integer programming problems; moreover, it can be improved by future research.