Hybrid Rounding Techniques for Knapsack Problems

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 powerful ways of rounding. As an application of these techniques, 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. This linear complexity bound gives a substantial improvement of the best previously known polynomial bounds.
19 LaTeX pages

Keywords

Computational Complexity, Discrete Mathematics, Data Structures and Algorithms, F.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/99279

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0305002
 http://arxiv.org/abs/cs/0305002
 Discrete Applied Mathematics, 154:4 (2006) 640-649
 doi:10.1016/j.dam.2005.08.004

Collections

arXiv