Hybrid rounding techniques for knapsack problems

DOI10.1016/J.DAM.2005.08.004zbMATH Open1120.90050arXivcs/0305002OpenAlexW2159846562WikidataQ62614593 ScholiaQ62614593MaRDI QIDQ2489957FDOQ2489957

Authors: Monaldo Mastrolilli, Marcus Hutter 

Publication date: 28 April 2006

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

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.

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

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

zbMATH Keywords

Dynamic programmingKnapsack problemsApproximation schemesArithmetic and geometric rounding

Mathematics Subject Classification ID

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

Cites Work

• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximation algorithms for knapsack problems with cardinality constraints
• Time bounds for selection
• Linear time algorithms for some separable quadratic programming problems
• Heuristic algorithms for the multiple knapsack problem
• Title not available (Why is that?)
• Hybrid rounding techniques for knapsack problems

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
• Title not available (Why is that?)

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)