ICS Theory Group

ICS 269, Winter 2006: Theory Seminar

Mar 10, 2006, in CS 253

Strip Packing with Precedence Constraints and Release Times

Authored by: John Augustine, Sudarshan Banerjee, Sandy Irani

Presented by John Augustine


This paper examines two variants of strip packing: when the rectangles to be placed have precedence constraints and when the rectangles have release times. Strip packing can be used to model scheduling problems in which tasks require a contiguous subset of identical resources that are arranged in a linear topology. The particular variants studied here are motivated by scheduling tasks for dynamically reconfigurable Field-Programmable Gate Arrays (FPGAs). For the case in which tasks have precedence constraints, we give an O(log n) approximation, where n is the number of tasks. We also give a 3-approximation for the special case in which all the rectangles to be placed have uniform height. For release times, we provide an asymptotic polynomial time (1+ε)-approximation scheme. We make the standard assumption that the rectangles have height at most 1. In addition, we also require widths to be in (&epsilonn, 1]. Our algorithm runs in time polynomial in n, 1/ε, and 1/&epsilonn.