2002/10/14 by Janos Csirik, János Csirik, David S. Johnson +12 · 1 citation
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #F.2.2 G.3 #FOS: Computer and information sciences #Manufacturing Process and Optimization #Optimization and Packing Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0210013
72 pages
arxiv created 2002/10/14 · openalex publication_date 2002/10/14 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we present a theoretical analysis of the deterministic on-line \em Sum of Squares algorithm (SS) for bin packing introduced and studied experimentally in \citeCJK99, along with several new variants. SS is applicable to any instance of bin packing in which the bin capacity B and item sizes s(a) are integral (or can be scaled to be so), and runs in time O(nB). It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, SS also has sublinear expected waste. For any discrete distribution where the optimal expected waste is bounded, SS has expected waste at most O(log n). In addition, we discuss several interesting variants on SS, including a randomized O(nBlog B)-time on-line algorithm SS^*, based on SS, whose expected behavior is essentially optimal for all discrete distributions. Algorithm SS^* also depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution F, just what is the growth rate for the optimal expected waste. This article is a greatly expanded version of the conference paper \citesumsq2000.