Applications and extensions of the bin packing problem

Abstract

Bin packing is a classic optimization problem with many applications and variants. In its basic form, the goal is to pack items of different sizes in the range (0,1] into the minimum number of unit capacity bins. In doing so, an "offline" algorithm has access to all items before packing them, while an "online" algorithm receives items one by one and places each item into a bin without any knowledge about the forthcoming items. In this thesis, we study two variants of bin packing: square packing, and fault-tolerant bin packing. Our goal is to design the algorithms that work well under the worst-case scenarios, where algorithms are evaluated based on the approximation factor (in offline setting), and competitive ratio (in online setting).

In the "square packing problem", items are squares of various side lengths, and bins are unit squares. We study this problem in both offline and online settings. Unlike previous work, we allow an algorithm to rotate items by any degree. This modification is consistent with the applications of square packing in stock cutting. We prove that the offline problem is NP-Hard and provide an asymptotic polynomial-time approximation scheme (APTAS) under an augmented resource setting. For the online setting, we present an online algorithm with a competitive ratio of at most 2.306. We also introduce an online algorithm with a competitive ratio of at most 1.897 for a related problem where the goal is to pack "tans" (half-square triangles) into unit squares.

In the "fault-tolerant bin packing problem", items represent replicas of tenants, and bins are uniform capacity servers. As servers fail regularly, a valid packing should tolerate the failure of a certain number of bins. Applications of this problem are online as tenant hosting requests are made sequentially. The best existing online algorithm has a competitive ratio of at most 2, which works in a setting where bins fail only after packing process is concluded. We study a more practical setting where the bin failures might happen during the packing process, and introduce an algorithm with an improved competitive ratio of at most 1.75 for this general setting.