Approximation schemes for knapsack problems with shelf divisions

DOI10.1016/J.TCS.2005.10.036MaRDI QIDQ818116zbMATH OpenOpenAlexFDO

Authors Eduardo C. Xavier, Flávio K. Miyazawa

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

approximation algorithmsapproximation schemesknapsack problemshelf packing

Mathematics Subject Classification ID

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

Recommendations

• A one-dimensional bin packing problem with shelf divisions
• A note on dual approximation algorithms for class constrained bin packing problems
• Polynomial time approximation schemes for class-constrained packing problems
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• scientific article; zbMATH DE number 1670546

Cites work

• A two-phase roll cutting problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Bin packing can be solved within 1+epsilon in linear time
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• scientific article; zbMATH DE number 5158520 (Why is no real title available?)
• scientific article; zbMATH DE number 1445306 (Why is no real title available?)
• Polynomial time approximation schemes for class-constrained packing problems
• The constrained compartmentalised knapsack problem
• The one dimensional Compartmentalised Knapsack problem: a case study

Cited in

(9)

• Utilizing shelve slots: Sufficiency conditions for some easy instances of hard problems
• Maximum coverage with cluster constraints: an LP-based approximation technique
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• On the approximability of the two-phase knapsack problem
• The class constrained bin packing problem with applications to video-on-demand
• A one-dimensional bin packing problem with shelf divisions
• PACKING SHELVES WITH ITEMS THAT DIVIDE THE SHELVES' LENGTH: A CASE OF A UNIVERSAL NUMBER PARTITION PROBLEM
• A note on dual approximation algorithms for class constrained bin packing problems
• The constrained compartmentalized knapsack problem: mathematical models and solution methods

Describes a project that uses

Uses Software

• Knapsack

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

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