Hybrid rounding techniques for knapsack problems |
| |
Authors: | Monaldo Mastrolilli |
| |
Institution: | IDSIA, Galleria 2, 6928 Manno, Switzerland |
| |
Abstract: | We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and more powerful ways of rounding. Moreover, we present a linear-storage polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. These linear complexity bounds give a substantial improvement of the best previously known polynomial bounds A. Caprara, et al., Approximation algorithms for knapsack problems with cardinality constraints, European J. Oper. Res. 123 (2000) 333-345]. |
| |
Keywords: | Knapsack problems Approximation schemes Arithmetic and geometric rounding Dynamic programming |
本文献已被 ScienceDirect 等数据库收录! |
|