Ratio combinatorial programs

We consider here a combinatorial optimization problem where the objective function is a ratio of two linear functions. One way of solving this problem is to solve repeatedly an auxiliary problem with a parameterized linear objective function. In this paper we relate this method to Newton's method for solving equations and present a modification of this algorithm which solves the ratio problem ϵ-approximately by repeatedly solving the auxiliary linear problems with the same accuracy. We demonstrate, by reporting results of extensive computational experiments, that the above modified algorithm for the ϵ-approximate knapsack problem performs extremely well in practice.