  We study the strip packing problem, a classical packing problem which
generalizes both bin packing and makespan minimization. Here we are given a set
of axis-parallel rectangles in the two-dimensional plane and the goal is to
pack them in a vertical strip of a fixed width such that the height of the
obtained packing is minimized. The packing must be non-overlapping and the
rectangles cannot be rotated. A reduction from the partition problem shows that
no approximation better than 3/2 is possible for strip packing in polynomial
time (assuming P$\neq$NP). Nadiradze and Wiese [SODA16] overcame this barrier
by presenting a $(\frac{7}{5}+\epsilon)$-approximation algorithm in
pseudo-polynomial-time (PPT). As the problem is strongly NP-hard, it does not
admit an exact PPT algorithm. In this paper, we make further progress on the
PPT approximability of strip packing, by presenting a
$(\frac43+\epsilon)$-approximation algorithm. Our result is based on a
non-trivial repacking of some rectangles in the \emph{empty space} left by the
construction by Nadiradze and Wiese, and in some sense pushes their approach to
its limit. Our PPT algorithm can be adapted to the case where we are allowed to
rotate the rectangles by $90^\circ$, achieving the same approximation factor
and breaking the polynomial-time approximation barrier of 3/2 for the case with
rotations as well.
