\documentclass[12pt]{article}
\usepackage{a4wide}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{defn}{Definition}

\title{A tight analysis of \\ Brown-Baker-Katseff sequences\\ for online strip packing}
\author{W.~Kern and J.J.~Paulus}
\date{}

\begin{document}
\setcounter{page}{109}

\maketitle

%{\abstract{We study certain adversary sequences for online strip packing which were first designed and investigated by Brown, Baker and Katseff \cite{BBK82}. We determine the optimal competitive ratio for packing such Brown-Baker-Katseff sequences online. As a byproduct of our result, we get a new lower bound of $\rho \ge 3/2+\sqrt{33}/6 \approx 2.457$ for the competitive ratio of online strip packing.}}

\parskip=0.2cm
\parindent=0cm

\section{Abstract}
In the two-dimensional strip packing problem a number of rectangles have to be packed without rotation or overlap into a strip such that the height of the strip used is minimum. The width of the rectangles is bounded by $1$ and the strip has width $1$ and infinite height. Baker, Coffman and Rivest \cite{BCR80} show that this problem is NP-hard.

We study the online version of this packing problem. In the online version the rectangles are given to the online algorithm one by one from a list, and the next rectangle is given as soon as the current rectangle is irrevocably placed into the strip. To evaluate the performance of an online algorithm we employ competitive analysis. For a list of rectangles $L$, the height of a strip used by online algorithm $A$ and by the optimal solution is denoted by $A(L)$ and $OPT(L)$, respectively. The optimal solution is not restricted in any way by the ordering of the rectangles in the list. Competitive analysis measures the absolute worst-case performance of online algorithm $A$ by its competitive ratio $\sup_{L}\{A(L)/OPT(L)\}$.

Regarding the upper bound on the competitive ratio for online strip packing, recent advances have been made by Ye, Han and Zhang \cite{YHZ08} and Hurink and Paulus \cite{HP08b}. Independently they present an online algorithm with competitive ratio $7/2+\sqrt{10}\approx6.6623$, that is a modification of the well known shelf algorithm. We refer to these two papers for a more extensive overview of the literature.


In the early 80's, Brown, Baker and Katseff \cite{BBK82} derived a lower bound $\rho \ge 2$ on the competitive ratio of any online algorithm by constructing certain (adversary) sequences in a fairly straightforward way. These sequences were further studied by Johannes \cite{J06} and Hurink and Paulus \cite{HP08a}, who derived improved lower bounds of 2.25 and 2.43, \emph{resp.} (Both results are computer aided and presented in terms of online parallel machine scheduling, a closely related problem.) The paper of Hurink and Paulus \cite{HP08a} also presents an upper bound of $ \rho \le 2.5$ for packing such ``Brown-Baker-Katseff sequences'' . The purpose of our present paper is to propose a potential function approach that allows us to close the gap between 2.43 and 2.5. We present a tight analysis, showing that Brown-Baker-Katseff sequences can be packed online with competitive ratio $\rho = 3/2 + \sqrt{33}/6$ and that this is best possible. As a byproduct we obtain a new lower bound $\rho \approx 2.457$ for online strip packing. 



\section*{Acknowledgment}
Part of this research has been funded by the Dutch BSIK/BRICKS project.

\begin{thebibliography}{99}  

\bibitem{BCR80}
{\sc Baker~B.S., Coffman~E.G. and Rivest R.L.} (1980). {\em Orthogonal packings in two-dimensions.} SIAM Journal on Computing 9:846-855.

\bibitem{BBK82}
{\sc Brown~D.J., Baker~B.S. and Katseff~H.P.} (1982). {\em Lower bounds for on-line two-dimensional packing algorithms.} Acta Informatica 18:207-225.

\bibitem{HP08a}
{\sc Hurink~J.L. and Paulus~J.J.} (2008). {\em Online scheduling of parallel jobs on two machines is 2-competitive.} Operations Research Letters 36:51-56.

\bibitem{HP08b}
{\sc Hurink~J.L. and Paulus~J.J.} (2008). {\em Online algorithm for parallel job scheduling and strip packing.} Lecture Notes in Computer Science (WAOA 2007) 4927:67-74.

\bibitem{J06}
{\sc Johannes~B.} (2006) {\em Scheduling parallel jobs to minimize the makespan.} Journal of Scheduling 9:433-452.

\bibitem{YHZ08}
{\sc Ye~D., Han~X. and Zhang~G.} (2009) {\em A note on online strip packing.} Journal of Combinatorial Optimization, in press, doi:10.1007/s10878-007-9125-x.

\end{thebibliography}

\end{document}

BBK82
