|
 
|
[BIL00] Computational experience with a 1/2-approximation algorithm for the hyperbolic 0-1 knapsack problem
Rapport Scientifique : Date de dépot: 2000/01/01, (Tech. Rep.: CEDRIC-00-105)
motcle:
Résumé:
The hyperbolic 0-1 knapsack problem (HKP)
consists to obtain a 0-1 solution that maximizes
a linear fractional objective function
under the constraint of one linear inequality.
We propose in this paper a linear
programming-based method to obtain in polynomial
time a 1/2-approximate solution to (HKP).
The method is based on the solution of the
continuous relaxation of (HKP) obtained by
removing the integrality constraints on the
variables. Moreover we report some computational
results which show that the method allows
approximate solutions to be found quickly
with a small relative gap compared to the
optimum (between 0.05% and 2.5%) for instances
comprising up to 10000 variables.
BibTeX
| @techreport { | |||
| BIL00, | |||
| title | = | "{Computational experience with a 1/2-approximation algorithm for the hyperbolic 0-1 knapsack problem}", | |
| author | = | "A. Billionnet", | |
| number | = | "{CEDRIC-00-105}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-01-2000}, | |
| } | |||
