Approximation schemes for packing with item fragmentation

DOI10.1007/S00224-007-9082-XMaRDI QIDQ927410zbMATH OpenOpenAlexFDO

Authors Hadas Shachnai, Tami Tamir, 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

AlgorithmsBin packingItem fragmentationLinear programmingPolynomial time approximation schemes

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Approximation and Online Algorithms
• Fast Asymptotic FPTAS for Packing Fragmentable Items with Costs
• scientific article; zbMATH DE number 1830744
• Analysis of transmissions scheduling with packet fragmentation
• Bin packing with fragmentable items: presentation and approximations

Cites work

• A new polynomial-time algorithm for linear programming
• Bin packing can be solved within 1+epsilon in linear time
• Complexity of fragmentable object bin packing and an application
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1830744 (Why is no real title available?)
• scientific article; zbMATH DE number 2114378 (Why is no real title available?)
• scientific article; zbMATH DE number 1405790 (Why is no real title available?)
• Introduction to algorithms.
• Minimizing makespan and preemption costs on a system of uniform machines
• Parallel Processor Scheduling with Limited Number of Preemptions
• Preemptive scheduling with position costs
• Scheduling with deadlines and loss functions
• Smoothed analysis of termination of linear programming algorithms
• The many facets of linear programming
• Using fast matrix multiplication to find basic solutions

Cited in

(18)

• Complexity of fragmentable object bin packing and an application
• Bin packing problem with conflicts and item fragmentation
• Offline black and white bin packing
• Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems
• New formulations for variable cost and size bin packing problems with item fragmentation
• A study on load-balanced variants of the bin packing problem
• Approximation schemes for packing splittable items with cardinality constraints
• Improved results for a memory allocation problem
• A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation
• Analysis of transmissions scheduling with packet fragmentation
• On Packing Splittable Items with Cardinality Constraints
• Mathematical programming algorithms for bin packing problems with item fragmentation
• Exactly solving packing problems with fragmentation
• scientific article; zbMATH DE number 1830744 (Why is no real title available?)
• An improved approximation scheme for variable-sized bin packing
• Fast Asymptotic FPTAS for Packing Fragmentable Items with Costs
• Approximation and Online Algorithms
• The basic train makeup problem in shunting yards

This page was built for publication: Approximation schemes for packing with item fragmentation

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