A fast asymptotic approximation scheme for bin packing with rejection

DOI10.1016/j.tcs.2007.10.042zbMath1136.68057OpenAlexW2143410025WikidataQ65553912 ScholiaQ65553912MaRDI QIDQ2481948

José R. Correa, Wolfgang W. Bein, Xin Han

Publication date: 15 April 2008

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

Full work available at URL: http://hdl.handle.net/10533/139324

zbMATH Keywords

knapsack problembin packingapproximation schemerejection penalty

Mathematics Subject Classification ID

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

Related Items (7)

On the generalized bin packing problem ⋮ An AFPTAS for variable sized bin packing with general activation costs ⋮ Nature inspired genetic algorithms for hard packing problems ⋮ Bin packing with general cost structures ⋮ Bin packing with controllable item sizes ⋮ Unnamed Item ⋮ Offline black and white bin packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 71/60 theorem for bin packing
• Bin packing can be solved within 1+epsilon in linear time
• Preemptive scheduling with rejection
• Bin packing problems with rejection penalties and their dual problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Variable Sized Bin Packing
• An Efficient Approximation Scheme for Variable-Sized Bin Packing
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Multiprocessor Scheduling with Rejection
• Bin Packing with Rejection Revisited
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

This page was built for publication: A fast asymptotic approximation scheme for bin packing with rejection