English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

Improved Pseudo-Polynomial-Time Approximation for Strip Packing