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

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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