Hybrid Rounding Techniques for Knapsack Problems

Simple item page
dc.creatorMastrolilli, Monaldo
dc.creatorHutter, Marcus
dc.date2003-05-02
dc.date.accessioned2026-07-07T06:33:41Z
dc.date.available2026-07-07T06:33:41Z
dc.descriptionWe 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.
dc.description19 LaTeX pages
dc.identifierhttps://arxiv.org/abs/cs/0305002
dc.identifierhttp://arxiv.org/abs/cs/0305002
dc.identifierDiscrete Applied Mathematics, 154:4 (2006) 640-649
dc.identifierdoi:10.1016/j.dam.2005.08.004
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/99279
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subjectF.2
dc.titleHybrid Rounding Techniques for Knapsack Problems
dc.typetext

Files

Collections

arXiv