Hybrid rounding techniques for knapsack problems

DOI10.1016/j.dam.2005.08.004zbMath1120.90050arXivcs/0305002OpenAlexW2159846562WikidataQ62614593 ScholiaQ62614593MaRDI QIDQ2489957

Marcus Hutter, Monaldo Mastrolilli

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)

Related Items (6)

A new effective dynamic program for an investment optimization problem ⋮ Hybrid rounding techniques for knapsack problems ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ A faster FPTAS for knapsack problem with cardinality constraint ⋮ Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times ⋮ A faster FPTAS for knapsack problem with cardinality constraint

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Linear time algorithms for some separable quadratic programming problems
• Heuristic algorithms for the multiple knapsack problem
• Time bounds for selection
• Approximation algorithms for knapsack problems with cardinality constraints
• Hybrid rounding techniques for knapsack problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

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