Hybrid rounding techniques for knapsack problems
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|
|Source:||Discrete Applied Mathematics|
|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.