Approximation algorithms for fractional knapsack problems

Balas, 1980, An algorithm for large zero-one knapsack problems, Oper. Res., 28, 1130, 10.1287/opre.28.5.1130 A. Billionnet, Computational experience with a 12-approximation algorithm for the hyperbolic 0-1 knapsack problem, CEDRIC Technical Report No. 105, Conservatoire National des Arts et Métiers, Paris, 2000, 9p. Dantzig, 1957, Discrete variable extremum problems, Oper. Res., 5, 266, 10.1287/opre.5.2.266 Dinkelbach, 1967, On nonlinear fractional programming, Manag. Sci., 13, 492, 10.1287/mnsc.13.7.492 Hansen, 1991, Hyperbolic 0-1 programming and query optimization in information retrieval, Math. Program., 52, 255, 10.1007/BF01582890 Hashizume, 1987, Approximation algorithms for combinatorial fractional programming problems, Math. Program., 37, 255, 10.1007/BF02591737 D.S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, 1997. Ishii, 1977, Fractional knapsack problems, Math. Program., 13, 255, 10.1007/BF01584342 Lawler, 1979, Fast approximation algorithms for knapsack problems, Math. Oper. Res., 4, 339, 10.1287/moor.4.4.339 S. Martello, P. Toth, Knapsack Problems, Wiley, England, 1990, 296p. Megiddo, 1979, Combinatorial optimization with rational objective functions, Math. Oper. Res., 4, 414, 10.1287/moor.4.4.414 A. Nagih, Sur la résolution des problèmes fractionnaires en variables 0-1, Thèse de Doctorat, Université Paris 13, France, juin 1996. Nagih, 2000, A Lagrangean decomposition for the 0-1 hyperbolic programming problem, Internat. J. Math. Algorithms, 1, 299 Papadimitriou, 1982 Radzik, 1998, Fractional combinatorial optimization, 429 Schaible, 1995, Fractional programming, 495