Skip navigation
Skip navigation

Hybrid rounding techniques for knapsack problems

Mastrolilli, Monaldo; Hutter, Marcus


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...[Show more]

CollectionsANU Research Publications
Date published: 2003-05-03
Type: Journal article
Source: Discrete Applied Mathematics
DOI: 10.1016/j.dam.2005.08.004


File Description SizeFormat Image
Mastrolilli and Hutter Hybrid Rounding Techniques 2006.pdf218.83 kBAdobe PDFThumbnail

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator