2025/10/30 by Jackson Bibbens, Bibbens, Jackson, Cooper Sigrist +7
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2510.26968
openalex publication_date 2025/10/30 · openalex created_date 2025/11/05 · openalex updated_date 2026/07/28
The online bin packing problem and its variants are regularly used to model server allocation problems. Modern concerns surrounding sustainability and overcommitment in cloud computing motivate bin packing models that capture costs associated with highly utilized servers. In this work, we introduce the green bin packing problem, an online variant with a linear cost β for filling above a fixed level G. For a given instance, the goal is to minimize the sum of the number of opened bins and the linear cost. We show that when βG ≤ 1, classical online bin packing algorithms such as FirstFit or Harmonic perform well, and can achieve competitive ratios lower than in the classic setting. However, when βG > 1, new algorithmic solutions can improve both worst-case and typical performance. We introduce variants of classic online bin packing algorithms and establish theoretical bounds, as well as test their empirical performance.