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

Approximation schemesArithmetic and geometric roundingDynamic programmingKnapsack problems

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 1182767 (Why is no real title available?)
• Hybrid rounding techniques for knapsack problems
• Linear time algorithms for some separable quadratic programming problems
• Time bounds for selection

Cited in

(10)

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

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)