## 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

Abstract:

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 (&epsilon_{n}, 1]. Our algorithm runs in time
polynomial in *n*, 1/ε, and 1/&epsilon_{n}.