Approximation schemes for knapsack problems with shelf divisions

DOI10.1016/j.tcs.2005.10.036zbMath1090.90168OpenAlexW2139494719MaRDI QIDQ818116

Flávio K. Miyazawa, Eduardo Candido Xavier

Publication date: 24 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.036

zbMATH Keywords

knapsack problemapproximation schemesapproximation algorithmsshelf packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ The constrained compartmentalized knapsack problem: mathematical models and solution methods ⋮ The class constrained bin packing problem with applications to video-on-demand ⋮ A one-dimensional bin packing problem with shelf divisions ⋮ On the approximability of the two-phase knapsack problem ⋮ A note on dual approximation algorithms for class constrained bin packing problems ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique

Uses Software

• Knapsack

Cites Work

• The constrained compartmentalised knapsack problem
• Bin packing can be solved within 1+epsilon in linear time
• Polynomial time approximation schemes for class-constrained packing problems
• Approximation algorithms for knapsack problems with cardinality constraints
• A two-phase roll cutting problem
• The one dimensional Compartmentalised Knapsack problem: a case study
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation schemes for knapsack problems with shelf divisions