BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260920T002230Z
UID:Seminar-networks-1136@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Giorgos Christodoulou:MAILTO:G.Christodoulou@liverpool.ac.uk
DTSTART:20210624T120000
DTEND:20210624T130000
SUMMARY:Networks and Distributed Computing Series
DESCRIPTION:Malin Rau: A Tight (3/2 + epsilon)-Approximation for Skewed Strip Packing\n\nIn the Strip Packing problem, we are given a vertical half-strip $[0,W]\times [0,+\infty)$ and a collection of open rectangles of width at most $W$.\nOur goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height $OPT$ spanned by the packing is as small as possible.\nIt is NP-hard to approximate this problem within a factor $(3/2-\epsilon)$ for any constant $\epsilon>0$ by a simple reduction from the Partition problem, while the current best approximation factor for it is (5/3+\epsilon).\n\nIt seems plausible that Strip Packing admits a $(3/2+\epsilon)$-approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter $\delta>0$, we call large the rectangles with width at least $\delta W$ and height at least $\delta OPT$, and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, it is NP-hard to approximate within a factor $(3/2-\epsilon)$ and we provide an (almost) tight $(3/2+\eps)$-approximation algorithm.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1136
LOCATION:
END:VEVENT
END:VCALENDAR