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

DOI10.1016/J.DISOPT.2010.03.003MaRDI QIDQ429647zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 2086931
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
• On the two-dimensional knapsack problem
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A structural lemma in 2-dimensional packing, and its implications on approximability
• Bin packing can be solved within 1+epsilon in linear time
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
• Integer Programming with a Fixed Number of Variables
• Maximizing the total profit of rectangles packed into a rectangle
• On the two-dimensional knapsack problem
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• The multiple subset sum problem

Cited in

(16)

• 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
• Two-dimensional knapsack for circles
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• Faster approximation schemes for the two-dimensional knapsack problem
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
• On the two-dimensional knapsack problem
• Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem
• Tight complexity bounds for the two-dimensional real knapsack problem
• On the approximability of the two-phase knapsack problem
• Approximation algorithms for a two-phase knapsack problem
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
• scientific article; zbMATH DE number 2086931 (Why is no real title available?)
• scientific article; zbMATH DE number 444958 (Why is no real title available?)

This page was built for publication: An approximation scheme for the two-stage, two-dimensional knapsack problem

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