An Efficient Approximation Scheme for Variable-Sized Bin Packing

DOI10.1137/0216012zbMath0618.90081OpenAlexW2032522336MaRDI QIDQ3755240

Frank D. Murgolo

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216012

zbMATH Keywords

NP-completebin packingapproximation schemeellipsoid methodasymptotic performance ratio

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (28)

Accelerating column generation for variable sized bin-packing problems ⋮ An AFPTAS for variable sized bin packing with general activation costs ⋮ Online variable-sized bin packing ⋮ Unnamed Item ⋮ Approximation algorithms for extensible bin packing ⋮ Hybrid Ant Colony Optimization Algorithms—Behaviour Investigation Based on Intuitionistic Fuzzy Logic ⋮ Security-aware database migration planning ⋮ A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts ⋮ Bin packing with general cost structures ⋮ Vector bin packing with multiple-choice ⋮ Efficient algorithms for the offline variable sized bin-packing problem ⋮ Branch-and-price and beam search algorithms for the variable cost and size bin packing problem with optional items ⋮ A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem ⋮ An improved approximation scheme for variable-sized bin packing ⋮ A fast asymptotic approximation scheme for bin packing with rejection ⋮ Relaxations and exact solution of the variable sized bin packing problem ⋮ Variable neighbourhood search for the variable sized bin packing problem ⋮ An exact algorithm for the type-constrained and variable sized bin packing problem ⋮ An on-line algorithm for variable-sized bin packing ⋮ On the approximability of the two-phase knapsack problem ⋮ Heuristics for the variable sized bin-packing problem ⋮ Variable sized online interval coloring with bandwidth ⋮ Cutting optimization with variable-sized stock and inventory status data ⋮ Approximation algorithms for partitioning small items in unequal bins to minimize the total size ⋮ Unnamed Item ⋮ Algorithms for the variable sized bin packing problem ⋮ Offline black and white bin packing ⋮ A bin packing problem with over-sized items

This page was built for publication: An Efficient Approximation Scheme for Variable-Sized Bin Packing