Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Approximation algorithms for a three-dimensional orthogonal knapsack problem

SpeakerFlorian Diedrich

Co-authorsRolf Harren, Klaus Jansen and Ralf Thoele

We study non-overlapping axis-parallel packings of three-dimensional boxes with profits into a dedicated bigger box where rotation is forbidden; we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms with approximation ratios 9+ε and 8+ε as well as an algorithm with approximation ratio 7+ε that uses more sophisticated techniques. To our best knowledge, these are the smallest absolute approximation ratios for the problem under consideration.

There is also a connection to scheduling; we can imagine a scenario where we wish to choose the most profitable jobs which are to be executed in a connected mesh system. From this perpective, the first two dimensions constitute the geometry of the mesh system while the third dimensions corresponds to the time.