Hybrid rounding techniques for knapsack problems

DOI10.1016/J.DAM.2005.08.004MaRDI QIDQ2489957zbMATH OpenOpenAlexWikidataFDO

Authors Monaldo Mastrolilli, Marcus Hutter

Publication date 28 April 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0305002

zbMATH Keywords

Dynamic programmingKnapsack problemsApproximation schemesArithmetic and geometric rounding

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

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 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 linear complexity bound gives a substantial improvement of the best previously known polynomial bounds.

Recommendations

• scientific article; zbMATH DE number 1839478
• scientific article; zbMATH DE number 988191
• A hybrid method for solving nonlinear knapsack problems
• scientific article; zbMATH DE number 3900494
• Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem
• Une approche hybride pour le sac à dos multidimensionnel en variables 0–1
• A hybrid algorithm for the unbounded knapsack problem
• Approximate And Exact Solution Methods For The Hyperbolic 0-1 Knapsack Problem

Cites work

• scientific article; zbMATH DE number 1182767 (Why is no real title available?)
• Approximation algorithms for knapsack problems with cardinality constraints
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Heuristic algorithms for the multiple knapsack problem
• Hybrid rounding techniques for knapsack problems
• Linear time algorithms for some separable quadratic programming problems
• Time bounds for selection

Cited in

(8)

• An FPTAS for budgeted laminar matroid independent set
• Hybrid rounding techniques for knapsack problems
• A faster FPTAS for knapsack problem with cardinality constraint
• A faster FPTAS for knapsack problem with cardinality constraint
• Approximation schemes for machine scheduling with resource (in-)dependent processing times
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• A new effective dynamic program for an investment optimization problem
• scientific article; zbMATH DE number 1839478 (Why is no real title available?)

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Hybrid rounding techniques for knapsack problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489957)