PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2609.07913v1cs.DS

TL;DR

Dynamic square bin packing must handle arrivals and departures while minimizing the peak number of active bins, with migration between bins forbidden. This paper uses a two-list algorithm and tighter NFDH area analysis to improve upper bounds for general and restricted square sizes. The resulting bounds are at most 3.918, 3.356, and 2.211 for general, unit-fraction, and power-fraction squares, respectively.

  • Problem

    Dynamic square bin packing asks how to minimize the peak number of active bins as squares arrive and depart, when departure times are unknown and migration between bins is forbidden.

    Source: §1 · p. 1

  • Method

    The paper partitions squares into two lists for its general algorithm and tightens NFDH occupied-area analysis for the general and restricted settings.

    Source: §1 · p. 2, §4 · p. 11

  • Results

    The upper bounds are 3.918 for general squares, 3.356 for unit-fraction squares, and 2.211 for power-fraction squares, improving the prior bounds 4.2154, 3.9654, and 2.4842, respectively.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The area bounds in Sections 3 and 4 are tight, so improving these ratios requires a different algorithm or a finer way of combining the bounds.

    Source: §6 · p. 15

    The tightness of the upper bound for the proposed SM and SMB algorithms remains open, including in the unit-fraction and general-square settings.

    Source: §6 · p. 16

Abstract

from arXiv · show

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.

1 Introduction

Prior work left the general-square upper bound at 4.2154, while this paper introduces improved bounds for general, unit-fraction, and power-fraction squares. Its general-case algorithm streamlines the item classification, and the restricted-case analyses use exact occupied-area computations.

Introduction

  • The model is online: squares arrive and depart, departure times are unknown, and migration between bins is forbidden, though items may be rearranged within a destination bin upon arrival.The objective is to minimize the peak number of concurrently active bins.Source: §1 · p. 1

Contributions

  • 3.918 replaces the longstanding 4.2154 upper bound for general squares, using two sublists and a tighter NFDH bin-area occupancy analysis.Epstein and Levy’s prior 4.2154 bound had remained the best known for general squares.Source: §1 · p. 2
  • 3.356 improves the unit-fraction square upper bound from 3.9654.The earlier 3.9654 bound was implicitly obtained from the analysis of Burcea, Wong, and Yung.Source: §1 · p. 2
  • 2.211 improves the power-fraction square competitive ratio from 2.4842, inherited from one-dimensional unit-fraction dynamic packing.Source: §1 · p. 2
  • Exact computations of minimum occupied area in levels that cannot fit a given item tighten both restricted-setting bounds and reduce the competitive gaps to 1.76 for general squares and 1.50 for unit-fraction squares.The 2.2307 lower bound of Epstein and Levy uses unit-fraction square inputs and therefore applies to both variants.Source: §1 · p. 2

2 Preliminaries

The preliminaries specify the dynamic packing model and competitive-analysis framework, then establish NFDH properties used to reason about whether multisets fit in one bin.

Dynamic square bin packing model

  • Items of side at most 1 arrive and depart at unannounced times; repacking is allowed only within the destination bin on arrival, never between bins.Source: §2 · p. 2

Competitive analysis

  • The competitive comparison uses each algorithm’s maximum active-bin count against OPT(σ), the maximum used by an offline algorithm that knows the sequence and may rearrange items across bins.The passage defines an asymptotic competitive ratio using these quantities, with an additive absolute constant.Source: §2 · p. 2

NFDH

  • NFDH sorts squares by non-increasing side length and packs them in horizontal levels; it fits a unit bin exactly when the level heights sum to at most 1.For analysis, its level decomposition can be considered in a width-1 strip of unbounded height.Source: §2 · p. 3

NFDH properties

  • If a sorted multiset fits by NFDH, replacing items with no larger ones or taking a subset preserves fit, supporting the per-bin invariant after departures.The comparison lemma assumes the replacement multiset has no more items and each sorted side length is no larger.Source: §2 · pp. 3–4

3 Dynamic Square Bin Packing

The general-square algorithm SMB divides items into two lists and combines separate packing strategies. Its analysis derives an NFDH occupied-area bound for small and medium squares, then uses bin-class occupancy bounds to control the number of bins.

Algorithm SMB

  • SMB partitions items into small-or-medium and big subsequences, then packs the first with SM and the second into empty bins.SM prioritizes S bins for small squares and M bins for medium squares; a bin that receives a small square becomes permanently classified as S.Source: §3 · pp. 4, 7

Analysis of SM

  • SM bounds bins in S using the occupied-area guarantee for failed small-square insertions, while bins in M are bounded using their medium-square occupancy.A small-square insertion failure gives an area bound of at least 4/9 for affected bins; a failed medium-square insertion into S invokes the 5/16 bound.Source: §3 · pp. 4, 6, 7

NFDH occupied-area bound

  • When NFDH fits X but fails after adding a square of side 1/2, the occupied area of X exceeds 5/16, and this bound is tight.The tight example uses five squares: two with side 1/4 + ε and three with side 1/4.Source: §3 · p. 5

Analysis of SM

  • The analysis considers the last bin-opening iteration and derives lower bounds on OPT from occupied area and the growth of S, yielding the stated bound for SM.S never shrinks, even when one of its bins becomes empty.Source: §3 · pp. 6–7

Algorithm and analysis

  • SMB’s two-list combination has constituent asymptotic ratios 747/256 and 1, whose sum gives 1003/256, approximately 3.918.The large-square list has ratio 1 because each bin holds at most one big square and a new bin opens only when all existing bins are occupied.Source: §3 · pp. 4, 8

4 Unit-Fraction Items

The section develops bounds for dynamic packing of unit-fraction squares, including a sharper competitive-ratio bound for SM based on sets that NFDH cannot pack together and an exact area-minimizing quantity. It also gives an asymptotic competitive-ratio upper bound for SMB of 4811105/1433976 ≈ 3.356.

4 Unit-Fraction Items

  • The section uses α⟨x, y⟩ as a lower bound on the area of the other squares in an NFDH level and constrains its optimal multiplicities to enable exact computation.The structural lemma bounds each n_i by k_i; exhaustive enumeration then computes exact values.Source: §4 · pp. 8–9
  • 1022131/2965284 is a lower bound on a(X) when NFDH cannot pack X together with one unit-fraction square, with every side at most 1/2.The section’s case analysis identifies this as the overall worst case.Source: §4 · pp. 9, 11
  • 119498/247107 is a lower bound on a(X) when NFDH cannot pack unit-fraction small or medium squares X together with a unit-fraction small square.The worst case occurs when X contains one square of side 1/2.Source: §4 · p. 11
  • 2.355 is the upper bound on SM’s asymptotic competitive ratio for unit-fraction squares with side at most 1.The exact bound is 3377129/1433976.Source: §4 · p. 11
  • The bound of Lemma 4.4 is best possible.Source: §4 · p. 12
  • For every ε > 0, some multiset X of unit-fraction squares with sides at most 1/2 fits in one bin under NFDH, but adding a square of side 1/2 makes NFDH fail.Source: §4 · p. 12
  • The Lemma 4.5 bound is best possible, with a(X) ≤ 119498/247107 + ε.Source: §4 · p. 12
  • For unit-fraction items, the two-list algorithms L1 and L2 have asymptotic competitive ratios 3377129/1433976 and 1, respectively.Source: §4 · p. 12
  • 4811105/1433976 ≈ 3.356 is an upper bound on SMB’s asymptotic competitive ratio for unit-fraction squares.Source: §4 · p. 12

5 Power-Fraction Items

The power-fraction analysis reduces the packing test to an area condition and bounds First-Fit's asymptotic competitive ratio by 2.211. Its worst case is identified by a specific sequence of parameters, while no algorithm can have a ratio below 2.

5 Power-Fraction Items

  • Merging four equal squares into a square of double side preserves area, and the procedure packs a multiset exactly when its total area is at most 1.The merging procedure fails if and only if the total area exceeds 1.Source: §5 · p. 13
  • Power-fraction square packing is equivalent to one-dimensional dynamic packing with item sizes 4^-j, so the prior 2.4842 First-Fit bound applies.The paper improves this inherited bound for the power-fraction setting.Source: §5 · p. 13
  • The worst case occurs when k ≥ 5, r1 = 1, r2 = 2, and r3 = 4.This parameter sequence yields the ratio 577087/261120 ≈ 2.211.Source: §5 · pp. 14–15
  • 2.211 is the asymptotic competitive-ratio upper bound for First-Fit on dynamic power-fraction squares.The bound is 577087/261120, which is less than 2.211.Source: §5 · p. 14
  • No algorithm has an asymptotic competitive ratio below 2 for dynamic power-fraction square packing.The cited lower-bound construction uses squares of sides 1/F and 1, with F chosen as a power of two.Source: §5 · p. 15

6 Conclusion

The paper improves upper bounds for dynamic packing of arbitrary, unit-fraction, and power-fraction squares. It also identifies tight area bounds and open questions about lower bounds for the proposed algorithms and the general case.

6 Conclusion

  • 3.918 for arbitrary squares, 3.356 for unit-fraction squares, and 2.211 for power-fraction squares are the paper's asymptotic competitive-ratio upper bounds.The arbitrary-squares bound improves the previous best-known 4.2154 bound.Source: §6 · p. 15
  • The 3.918 bound improves Epstein and Levy's 4.2154 bound, which had remained best-known for arbitrary squares.Source: §6 · p. 15
  • The area bounds in Sections 3 and 4 are tight, so improving the ratios requires a different algorithm or a finer combination of those bounds.Source: §6 · p. 15
  • Lower bounds for the proposed algorithms in unit-fraction and general-square settings remain open, as do stronger lower bounds for the general case.The best currently known lower bound for the general case uses only unit-fraction items.Source: §6 · p. 16

A APPENDIX – Power-Fraction Case Analysis

The appendix gives the detailed calculations for the power-fraction analysis and defines c2 as an absolute constant that does not affect the asymptotic ratio.

A APPENDIX – Power-Fraction Case Analysis

A.1 Case 1: k = 1.

In Case 1, construction stops at k = 1, so every earlier-indexed bin rejected the arriving item and contains no item smaller than 1/r1.

A.1 Case 1: k = 1.

  • When k = 1, no bin with index below b1 contains an item smaller than 1/r1, and each rejected the arriving item.Source: §A.1 · p. 17

A.2 Case 2: k = 2, r1 = 1.

The case yields an inequality relating l and b1.

A.2 Case 2: k = 2, r1 = 1.

A.3 Case 3: k ≥2, r1 ≥2.

The case combines Equation (7) or (6) with Equation (8) to obtain a result involving l + 1.

A.3 Case 3: k ≥2, r1 ≥2.

  • Combining Equations (7) or (6) and (8), we obtain l + 1.Source: §A.3 · p. 17

A.4 Case 4: k = 3, r1 = 1, r2 = 2.

The case combines inequalities to derive bounds involving b1 and b2.

A.4 Case 4: k = 3, r1 = 1, r2 = 2.

A.5 Case 5: k ≥3, r1 = 1, r2 ≥4.

Cases 5–8 derive inequalities relating l and the b-values to b1, with each case using a different set of r-conditions.

A.5 Case 5: k ≥3, r1 = 1, r2 ≥4.

  • The cited statements give two inequalities: 130/63 l + c2 ≥ b1 and 67/63 l + 17/16 ≥ b2.Source: §A.5 · p. 18

A.6 Case 6: k = 4, r1 = 1, r2 = 2, r3 = 4.

  • Case 6 presents a gamma-term relation for b3 and a resulting inequality involving b2.Source: §A.6 · pp. 18–19

A.7 Case 7: k ≥4, r1 = 1, r2 = 2, r3 ≥8.

  • 1024l + c2 ≥ b1, alongside the stated bound 1279/1020 l + 321/256 ≥ b2 in Case 7.Source: §A.7 · p. 19

A.8 Case 8: k ≥5, r1 = 1, r2 = 2, r3 = 4.

  • Case 8 gives 261120l + c2 ≥ b1 and states a bound for b2 as 82441/65280l + 20691/16384 ≥ b2.Source: §A.8 · pp. 19–20
Loading 2609.07913v1…