Skip navigation
Skip navigation

Hybrid rounding techniques for knapsack problems

Mastrolilli, Monaldo; Hutter, Marcus

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

CollectionsANU Research Publications
Date published: 2003-05-03
Type: Journal article
URI: http://hdl.handle.net/1885/15034
Source: Discrete Applied Mathematics
DOI: 10.1016/j.dam.2005.08.004

Download

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:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator