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.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Social welfare services and problem drinking : a comparative study of the use of social welfare services by problem drinking families and non-problem drinking families known to the main family agencies in the City of Winnipeg in September, 1962
Allard, T. S. (1963)This study took place in Winnipeg, Manitoba between October, 1962 and May, 1963, and was focused on the use of services by families active with one or more of the five main family agencies in this city, for the purpose of ... -
Shifting attentions in mathematics: developing problem solving abilities through problem-solving groups
McIntosh, Blaine (2011-08-12)The purpose of this study was to improve problem solving attitudes and abilities in students of mathematics through the exploration of John Mason’s general problem solving strategy and the use of problem solving groups, ...