Approximation schemes for packing with item fragmentation

DOI10.1007/s00224-007-9082-xzbMath1140.68548MaRDI QIDQ927410

Tami Tamir, Hadas Shachnai, Omer Yehezkely

Publication date: 6 June 2008

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9082-x

zbMATH Keywords

Algorithms; Linear programming; Bin packing; Item fragmentation; Polynomial time approximation schemes

Mathematics Subject Classification ID

68W25: Approximation algorithms

Related Items

The basic train makeup problem in shunting yards, Exactly solving packing problems with fragmentation, An improved approximation scheme for variable-sized bin packing, Offline black and white bin packing, Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems, Approximation schemes for packing splittable items with cardinality constraints, Improved results for a memory allocation problem

Cites Work

• A new polynomial-time algorithm for linear programming
• Minimizing makespan and preemption costs on a system of uniform machines
• Bin packing can be solved within 1+epsilon in linear time
• Using fast matrix multiplication to find basic solutions
• Smoothed analysis of termination of linear programming algorithms
• Complexity of fragmentable object bin packing and an application
• The many facets of linear programming
• Scheduling with Deadlines and Loss Functions
• Parallel Processor Scheduling with Limited Number of Preemptions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item