Hybrid Rounding Techniques for Knapsack Problems

Author:	Monaldo Mastrolilli and Marcus Hutter (2002)
Comments:	19 LaTeX pages
Subj-class:	Computational complexity; discrete mathematics; algorithms
ACM-class:	F.2.3
Report-no:	IDSIA-03-02

Keywords:

Abstract: 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 faster polynomial time approximation schemes that computes an approximate solution of any fixed accuracy in linear time. This linear complexity bounds give a substantial improvement of the best previously known polynomial bounds.

Table of Contents

1. Introduction
2. Rounding techniques for kKP
   • Arithmetic rounding
   • Geometric rounding
   • Parallel Arithmetic & Geometric rounding
3. An improved PTAS for kKP
   • Analysis of the Algorithm
4. An improved FPTAS for kKP
   • Dynamic programming for large items
   • Adding small items

BibTeX Entry

@Article{Hutter:02knapsack,
  author =       "Monaldo Mastrolilli and Marcus Hutter",
  number =       "IDSIA-03-02",
  institution =  "Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA)",
  title =        "Hybrid Rounding Techniques for Knapsack Problems",
  year =         "2002",
  address =      "Manno(Lugano), CH",
  journal =      "Special Issue of Discrete Applied Mathematics, submitted",
  abstract =     "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 faster
                  polynomial time approximation schemes that computes an approximate solution
                  of any fixed accuracy in linear time. This linear complexity bounds give a
                  substantial improvement of the best previously known polynomial bounds",
}