Hybrid rounding techniques for knapsack problems
-
Altmetric Citations
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]
Collections | ANU 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 |
Access Rights: | Open Access |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
Mastrolilli and Hutter Hybrid Rounding Techniques 2006.pdf | 218.83 kB | Adobe PDF |
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator