Article ID: | iaor20031609 |
Country: | Netherlands |
Volume: | 30 |
Issue: | 5 |
Start Page Number: | 336 |
End Page Number: | 342 |
Publication Date: | Oct 2002 |
Journal: | Operations Research Letters |
Authors: | Billionnet Alain |
Keywords: | knapsack problem |
We consider the combinatorial optimization problem where the objective function is the ratio of two linear functions. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. We propose for the original problem an approximation scheme based on the one hand upon an approximation scheme for the auxiliary problem and on the other hand upon a constant approximation algorithm for the original problem. As an example of the method we propose an