An approximation scheme for the two-stage, two-dimensional knapsack problem

DOI10.1016/j.disopt.2010.03.003zbMath1241.90102OpenAlexW2153325184MaRDI QIDQ429647

Alberto Caprara, Andrea Lodi, Michele Monaci

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.03.003

zbMATH Keywords

knapsack problempolynomial time approximation schemesshelf packing

Mathematics Subject Classification ID

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

Related Items

Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem, On the \(L\)-approach for generating unconstrained two-dimensional non-guillotine cutting patterns

Cites Work

• Unnamed Item
• Unnamed Item
• Maximizing the total profit of rectangles packed into a rectangle
• Bin packing can be solved within 1+epsilon in linear time
• On the two-dimensional knapsack problem
• The Multiple Subset Sum Problem
• Integer Programming with a Fixed Number of Variables
• A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing