From egc@research.bell-labs.com Sat Aug  2 15:54:09 1997
From: egc@research.bell-labs.com
Date: Sat, 2 Aug 97 09:51 EDT

Here are a couple of intriguing open problems in the analysis of
bin packing algorithms.

-Ed

##############################################

\documentstyle{article}
\begin{document}
\begin{center}
Open problems in one dimensional bin packing.
\end{center}
Find a $u,~0 < u < 1,$ such that the expected wasted space
${\rm E}W_n^{FF}(u)$ in the First Fit packing of $n$ items
drawn indpendently from $U(0,u)$ grows linearly in $n$ (or
more generally is $\Theta(n)$).  This result is thought to
hold for all such $u$, in fact.  Moreover, the corresponding
questions are open for Best Fit as well.  (Recall what is
known:  ${\rm E}W_n^{BF}(1) = \Theta(n^{1/2} \log^{3/4}n)$ (as
shown by Shor) and ${\rm E}W_n^{FF}(1) = \Theta(n^{2/3})$ (as
shown by Coffman, Johnson, Shor, and Weber).
\end{document}