previous home search |
LaTeX (51kb)
PostScript (596kb)
PDF (390kb)
Html/Gif
| contact up next |

## 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.

previous home search |
LaTeX (51kb)
PostScript (596kb)
PDF (390kb)
Html/Gif
| contact up next |

## Table of Contents

Introduction

Rounding techniques for kKP

- Arithmetic rounding
- Geometric rounding
- Parallel Arithmetic & Geometric rounding
An improved PTAS for kKP

- Analysis of the Algorithm
An improved FPTAS for kKP

- Dynamic programming for large items
- Adding small items

previous home search |
LaTeX (51kb)
PostScript (596kb)
PDF (390kb)
Html/Gif
| contact up next |

@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", }

previous home search |
LaTeX (51kb)
PostScript (596kb)
PDF (390kb)
Html/Gif
| contact up next |