CS Paper Radar

Improved Upper Bounds for Dynamic Bin Packing of General, Unit-Fraction, and Power-Fraction Squares

Miguel A. Mini, Flávio K. Miyazawa, Gabriel M. Silva, Yoshiko Wakabayashi

cs.DS ·submitted 2026-09-07 19:26 UTC · v1
theory

Abstract

This paper presents significant upper-bound improvements for dynamic 2D square bin packing, where square items arrive and depart over time and the objective is to minimize the peak number of concurrent active unit bins. In our model, repacking is permitted only within a destination bin upon item arrival; migration between active bins is strictly forbidden. By introducing a streamlined two-list algorithm and proving a tight $5/16$ occupied-area bound for Next-Fit Decreasing Height, we reduce the upper bound on the asymptotic competitive ratio for arbitrary squares from 4.2154 down to 3.918, breaking a longstanding theoretical ceiling. For restricted variants, we establish asymptotic competitive ratios of at most 3.356 for unit-fraction side lengths and 2.211 for power-fraction side lengths.

Comment
20 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Online Timely Bin Packing Revisited: A Simpler Algorithm with Optimality in Special Cases

cs.DS ·2026-11-06 ·Pei-Lin Chiang, Wing-Kai Hon, Ying-Chia Huang, Li-Tzu Yang
theory similarity 0.69
Abstract · 17 pages, 1 figure

Online Timely Bin Packing is a variant of classical online bin packing in which items arrive over time with sizes and deadlines. Packing an item may be deferred until its deadline, but once a collection of items is packed into a bin, the bin is closed and cannot be used again. The objective is to minimize the total number of bins used. The problem was introduced by Khattar in 2023. In 2025, Aminian proposed Discrete-Greedy, a deterministic online algorithm with a competitive ratio of exactly $2$, which remains the best-known upper bound. Its analysis is particularly simple; however, the algorithm requires maintaining a fractional simulation internally and may leave usable space in some bins unfilled. We propose Thrifty-Greedy, a simple deterministic online algorithm that does not require a fractional simulation. We prove that its competitive ratio is exactly $2$, matching the best-known upper bound. At the same time, the algorithm automatically achieves the optimal competitive ratio on two natural classes of inputs: it is $1$-competitive when all items have the same size, and $1.5$-competitive when every item has size in $\{1/3,2/3\}$. In contrast, Discrete-Greedy has a competitive ratio of at least $2$ on both classes.

0.19

Online Bin Packing with Dispatch Deadlines

cs.DS ·2026-11-05 ·Pei-Lin Chiang, Wing-Kai Hon, Kazuo Iwama, Li-Tzu Yang
published similarity 0.66
Abstract · 16 pages, 1 figure. Full version of a paper to appear in the 37th International Symposium on Algorithms and Computation (ISAAC 2026)

We study a generalization of online bin packing by introducing dispatch deadlines. Items arrive over time in an online fashion. Each item has an arrival time, a size in $(0,1]$, and a deadline, all of which are revealed only when the item arrives. The algorithm must immediately and irrevocably assign the item to a unit-capacity bin that has not yet been dispatched. Each bin must be dispatched no later than the earliest deadline of the items assigned to it, and once it is dispatched, it cannot be used for future items. The goal is to minimize the number of bins used. Applications arise naturally in logistics. Additionally, the offline version of this problem has appeared under several names, including the clique partition problem in weighted interval graphs and the BinSchedule problem. This problem is also a special case of online bin packing with conflicts and is closely related to online bin packing models with delay costs. We study the competitive ratios of several classical online bin packing algorithms when applied to this problem, and show that a similar hierarchy of competitive ratios carries over. Our main technical results are that the competitive ratio of First-Fit is exactly $16/7 \approx 2.28571$, and that no deterministic online algorithm has a competitive ratio less than $11/5 = 2.2$, showing that First-Fit is quite close to best possible. In addition, Next-Fit and Worst-Fit have competitive ratio exactly $3$, and every algorithm in the Any-Fit class has competitive ratio between $16/7$ and $3$.

0.36

A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

cs.CG ·2026-09-09 ·Nichlas Langhoff Rasmussen
theory similarity 0.64
Abstract · 13 pages. 5 figures

We consider online packing of axis-parallel squares into a unit-width strip under the Tetris and gravity constraints: An incoming square must be lowered from above along a monotonic downwards path until it reaches support from below. Fekete, Kamphans, and Schweer [Algorithmica, 2014] gave an algorithm with asymptotic competitive ratio $34/13\approx2.6154$ in this model. We present $\mathrm{AsymmetricSlots}$, a recursive algorithm based on splitting each slot into a wide and narrow subslot. The proof uses a local charging argument: squares that are large relative to its associated slot pay for the height they create with their own area, while smaller squares are balanced between the two subslots and may use a bounded temporary credit. For a suitable split parameter $p^\star$, we prove $\mathrm{AsymmetricSlots}{p^\star}(σ)\le 2.37332 \operatorname{OPT} (σ)+O(1)$ for every input sequence $σ$. Additionally, we show that the same framework gives an algorithm with asymptotic competitive ratio $O(κ)$ for rectangles of aspect ratio at most $κ$, and a matching $ Ω(κ)$ lower bound shows that the dependence on $κ$ is asymptotically optimal. For the square algorithm, we give a lower bound of $2$ on its asymptotic competitive ratio.

0.33

Busy Time Minimization with Preemption, Migration, and One Resource Requirement

cs.DS ·2026-09-19 ·Gruia Calinescu, Mozhengfu Liu
similarity 0.59
Abstract

We study the Busy Machine Time with Preemption and Migration and One Resource Requirement problem, motivated by energy minimization in cloud data centers. Given unlimited identical-capacity machines and jobs with release times, deadlines, processing times, and resource requirements, we allow free preemption and migration at integer times and seek to minimize total machine busy time. The problem is NP-hard, and previous results consist of a 2-approximation, 2-competitive algorithm for the case of uniform heights. We obtain a 22/9 < 2.445-approximation algorithm and a 2.5-competitive online algorithm, both running in O(n^2 log n) time. Our methods are based on new non-asymptotic performance bounds for the First Fit Decreasing algorithm for Bin Packing, and a new generalization of Span Minimization, the Huge-Tiny Busy Time problem, for which we present an exact offline algorithm and an optimal (3/2)-competitive deterministic online algorithm.

0.10

Additive $Ω(\log^* OPT)$ Gap for Bin Packing with Three Items per Bin

cs.DS ·2026-11-06 ·Ilan Doron-Arad
theory similarity 0.59
Abstract

We prove that bin packing is NP-hard to approximate within an additive factor of $o(\ls\OPT)$, even when all item sizes are arbitrarily close to $1/3$. This gives the first lower bound for bin packing with an additive factor that depends explicitly on the optimum value. In addition, we give a polynomial-time reduction from any bin packing instance into one with item sizes arbitrarily close to $1/3$, preserving its additive configuration-LP gap up to constant factors. Thus, in the sense of additive configuration LP gap and up to a constant, we confirm the conjecture that 3-partition instances are the hardest bin packing instances. In particular, we obtain an unconditional $Ω(\ls\OPT)$ gap for 3-partition instances. We build on the recent OpenAI construction that uses five items per bin and rules out any constant additive gap.

0.25

Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation

cs.CG cs.DS ·2026-11-03 ·Lucas de Oliveira Silva, Elisa Dell'Arriva, Flávio Keidi Miyazawa
similarity 0.59
Abstract

We study the geometric bin packing problem for simple polygonal regions, i.e., non-degenerate, connected, rational regions, in the minimum number of unit-square bins, allowing only translations. We even consider packing general non-convex objects, possibly with holes, where we can then pack smaller objects. Previous schemes cover squares (MOR'06), circles and other $L_p$-balls (Algorithmica'16), sufficiently skewed rectangles (Algorithmica'23), and convex fat objects with a constant number of distinct shapes under resource augmentation (arXiv'24, WAOA'23). The result for circles and other $L_p$-balls needs bin augmentation to obtain rational packing realizations. For restricted classes of $L$-shaped polygons, Gerlach et al. (SoCG'26) give constant worst-case guarantees, while for general non-convex objects, bounding-box reductions give just approximation factors that depend on fatness. Against this background, we present a general framework that provides asymptotic polynomial-time approximation schemes (APTAS) for bin packing of any fixed class of simple polygonal regions satisfying just two assumptions. First, covering any object by the grid cells intersecting its interior in any sufficiently fine square grid, relative to the object's bounding box, increases its area by at most a small fraction. Second, the class can be partitioned into a constant number of sequences such that each object in a sequence can be translated to fit inside every preceding object. In particular, certain classes of star-shaped polygons and more general polygonal regions, including some with simple holes, satisfy both assumptions. In addition, our framework does not require a bound on the objects' boundary complexity. We emphasize that our results require no bin augmentation whatsoever and yield explicit, exact rational packings of polynomial encoding length for all input objects.

0.29

Improved Approximation for Weighted $k$-Set Packing via a Simple Two-Phase Approach

cs.DS ·2026-11-16 ·Mehrshad Taziki, Rico Zenklusen
similarity 0.57
Abstract

Weighted $k$-set packing asks for a maximum-weight collection of pairwise disjoint sets, each of cardinality at most $k$. For every fixed $k\in\mathbb Z_{\geq1}$, we give a polynomial-time algorithm with approximation factor $\left(1- 1/{\sqrt3} \right)k+O(\log k) \approx 0.4226k + O(\log k)$, improving the previous best factor of $0.4621k + O(\sqrt{k})$ through a simple two-phase approach. In a first phase, our algorithm constructs a packing by processing random weight buckets of varying widths with an unweighted packing algorithm. We show that a small expected weight of this packing relative to the optimum forces a large expected total surplus in the optimum. Surplus quantifies the potential for improving a packing through star swaps. In the second phase, we solve and round a configuration LP to turn sufficiently large surplus into an increase in expected weight. Our procedure can easily be derandomized.

0.30

Load Balancing with Item Fragmentation and More Bins than Items: Linear-Time and Exact

cs.DS cs.DC ·2026-11-06 ·Ben Bals, Tomáš Flouri, Kassian Kobert, Solon P. Pissis, Leen Stougie
theory similarity 0.57
Abstract

We study a fundamental load-balancing problem in which $N$ items of strictly positive integer sizes with total size $W$ must be assigned to $B$ bins, with items allowed to be divided into integer-size fragments across bins. Each bin must receive a load of either $\lfloor W/B \rfloor$ or $\lceil W/B \rceil$, ensuring that the loads of any two bins differ by at most one unit. Under this constraint, the objective is to minimize the maximum number of distinct item fragments placed into any single bin. This problem is NP-hard and there exists an $(\mathrm{OPT}+1)$-approximation algorithm that runs in $O(N \log N + B)$ time [Kobert et al., 2014]. The existing algorithm is employed by several widely used production codes for phylogenetic reconstruction. Here, we focus on the case $B \ge N$, that is, bins are at least as numerous as items. This setting arises pervasively in modern parallel and distributed systems, as well as in iterative algorithms that rebalance their workload at every step. In this context, bins are machines or machine cores, and items represent computational tasks (jobs). Our central contribution is a remarkably simple $O(N)$-time algorithm that computes an optimal assignment in this setting; this assignment is encoded using $O(N)$ space. In particular, we prove that an optimum always exists in which every bin receives at most two fragments and provide a characterization of when one fragment per bin suffices. Our result strictly improves the $(\mathrm{OPT}+1)$-approximation of Kobert et al. in the many-bins setting and, together with it, yields a strongly polynomial-time $(\mathrm{OPT}+1)$-approximation algorithm for the general setting, as it removes the dependency on the number $B$ of bins.

0.26