Efficient Packing of Unit Squares in a Square

Abstract

Let $s(N)$ denote the edge length of the smallest square in which one can pack $N$ unit squares. A duality method is introduced to prove that $s(6)=s(7)=3$. Let $n_r$ be the smallest integer $n$ such that $s(n^2+1)\le n+{1/r}$. We use an explicit construction to show that $n_r\le 27r^3/2+O(r^2)$, and also that $n_2\le43$.