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

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

1,2 , Tomáš Flouri

3 , Kassian Kobert

4 , Solon P. Pissis

5 , and Leen Stougie

1 CWI, Amsterdam, The Netherlands 2 Vrije Universiteit, Amsterdam, The Netherlands 3 University College London, UK 4 Universität Bielefeld, Germany

arXiv:2611.09267v1 [cs.DS] 6 Nov 2026

5 The Cyprus Institute, Nicosia, Cyprus

November 9, 2026 Abstract We study a fundamental load-balancing problem in which 𝑁 items of strictly positive integer sizes with total size 𝑊 must be assigned to 𝐵 bins, with items allowed to be divided into integer-size fragments across bins. Each bin must receive a load of either ⌊𝑊/𝐵⌋ or ⌈𝑊/𝐵⌉, 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 (OPT + 1)-approximation algorithm that runs in O (𝑁 log 𝑁 + 𝐵) 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 𝐵 ≥ 𝑁, 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 (𝑁)-time algorithm that computes an optimal assignment in this setting; this assignment is encoded using O (𝑁) 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 (OPT + 1)-approximation of Kobert et al. in the many-bins setting and, together with it, yields a strongly polynomial-time (OPT + 1)-approximation algorithm for the general setting, as it removes the dependency on the number 𝐵 of bins.

1

1,2

1

Introduction

Balancing work across processing units is a fundamental problem in parallel and distributed computing, from early multiprocessors [Gra69, Cyb89] to modern many-core systems [ST19, LSS22]. As processor core counts grow, efficient utilization becomes increasingly important: a system draws substantial power whether its cores are busy or idle [BH07], so unused cores waste capacity, whereas shorter runtimes reduce total energy use [WL08]. The problem is becoming more acute as datasets grow across disciplines, increasing the work to be balanced: from large-scale simulations in high-performance and scientific computing [KK98, BD97, VGR03], through web-scale queries and MapReduce jobs in data systems [DG08, GARK11, KTR12] and rising traffic in communication networks [KSV03, CMSM+ 15], to billion-parameter models shared across accelerators in machine learning [LAP+ 14, MHH+ 22]. In such settings, the workload is often divisible and should be distributed evenly, while each processing unit may incur an overhead for every distinct (potentially fragmented) work unit it handles, motivating us to minimize the number of distinct units. This led us to study the following problem, which has been introduced and studied in [KFAS14]. Given 𝑁 items (jobs) of strictly positive integer sizes and total size 𝑊, assign them to 𝐵 bins (processors), with items allowed to be divided into integer-size fragments across bins. The load between bins must be as balanced as possible, that is, a load of either ⌊𝑊/𝐵⌋ or ⌈𝑊/𝐵⌉. Under this constraint, the objective is to minimize the maximum number of distinct item fragments placed into any single bin. A concrete application of balancing divisible load while limiting per-processor fragmentation arises in statistical phylogenomics [KYT20]. The input is a multiple sequence alignment, which can be viewed as a matrix: its rows correspond to taxa and its columns to homologous positions in their molecular sequences. Each column is called an alignment site. The alignment sites are typically grouped into partitions, with the sites in each partition analyzed under the same evolutionary model. For a fixed candidate phylogenetic tree, likelihood calculations at different sites are mutually independent, and their repeated evaluation dominates the cost of maximum-likelihood and Bayesian inference [Fel81]. Alignment sites can therefore be distributed across processors. Under the standard uniform-site cost model, assigning approximately the same number of sites to every processor balances the arithmetic workload. However, a processor also incurs partition-specific overhead for every partition from which it receives at least one site. The goal is thus to balance the number of sites while minimizing the maximum number of distinct partitions handled by any processor. Kobert et al. [KFAS14] formalized this task as the divisible load balance problem, which we will call here Load Balancing with Item Fragmentation (LBIF). In this formulation, the items are the partitions, the size of an item is its number of sites, and the bins are the processors. A partition may be divided among several processors, and each processor receives either ⌊𝑊/𝐵⌋ or ⌈𝑊/𝐵⌉ sites, where 𝑊 is the total number of sites and 𝐵 is the number of processors. The objective is to minimize the maximum number of partitions assigned to any one processor. Kobert et al. proved the problem to be NP-hard and gave an (OPT + 1)-approximation running in O (𝑁 log 𝑁 + 𝐵) time for 𝑁 partitions (items). Their algorithm is implemented in widely used phylogenetic software, including RAxML-NG [KDF+ 19] and ExaBayes [AKS14]. A related, data-dependent variant arises from the site-repeats optimization [KSF17]. For a node of the phylogenetic tree, a site’s subcolumn is its alignment column restricted to the taxa in the subtree rooted at that node. If two sites in the same partition have identical subcolumns, the intermediate likelihood at the root of that subtree is the same for both and needs to be computed only once. Consequently, workload is not determined by site count alone, and gives another variation of the load-balancing problem [SKFS16, MFS17]. In this paper, we study the case in which there are at least as many bins as items. In practice, bins may far outnumber items: a modern server may provide hundreds of cores, and a cluster many more, while potentially only a handful of large, divisible jobs are active at a time. The algorithm of Kobert et al. applies in this regime, but remains an approximation: it returns an assignment of value at most OPT + 1 and does not necessarily attain OPT. Moreover, its O (𝑁 log 𝑁 + 𝐵) running time depends on the number 𝐵 of bins. Since 𝐵 may be arbitrarily large relative to 𝑁, this bound may not be polynomial in 𝑁. In response, we show that, for every 𝐵 ≥ 𝑁, an optimal assignment in which every bin receives at most two fragments always exists. Furthermore, we construct such an assignment in O (𝑁) time using O (𝑁) space, and give an O (𝑁)-time arithmetic test that determines whether the optimum is one or two. Combined with the algorithm of Kobert et al. for 𝐵 < 𝑁, our result yields an (OPT + 1)-approximation for every 𝐵 that runs in O (𝑁 log 𝑁) time and is therefore strongly polynomial. Additionally, our algorithm is so simple that it is easy to implement, making it amenable to practical adoption (e.g., in the existing software [AKS14, KDF+ 19]). The O (𝑁) running time is also beneficial when assignments must be recomputed frequently. This occurs, for example, in fault-tolerant likelihood evaluation, 2

where data are redistributed whenever processors fail or become available [HKH+ 21]. Another application arises in Metropolis-coupled MCMC for Bayesian phylogenetic inference, which runs several interacting chains at different temperatures in parallel [ADHR04]. When the available cores outnumber the chains, the likelihood computation within each chain can be divided across independent alignment sites. Treating chains as divisible items and cores as bins yields a many-bins instance in which per-step work is balanced while the maximum number of chains handled by any core is minimized. Related work. Apart from the above-mentioned work motivating our study, we mention here literature on multiprocessor scheduling and bin packing. Load balancing is the most common target in classical multiprocessor scheduling, often under the name of makespan minimization. Indeed, the first theoretical results date back to the sixties [Gra66, Gra69]. The general problem on identical machines is NP-hard [Kar72]. However, preemptive jobs make the problem easy [McN59], and splittable (divisible) jobs, dividing jobs across identical machines without further constraints makes the problem trivial. Our problem is complicated by the objective of minimizing the maximum number of job fragments. Other works on splittable (divisible) scheduling [KSV03, Ev06, CMSM+ 15, DJ19] divide jobs into fragments across identical or unrelated machines to minimize the makespan, but with the number of fragments bounded [KSV03, Ev06] or penalized, for instance, through (batch) setup times [CMSM+ 15, DJ19]. As its name suggests, there is also a relation to bin packing with item fragmentation. In early work on this problem [MR01, STY08, SY07], as well as in later publications [BGW19, CC14, Eki21], fragmentation comes at a price: increasing cost or size. None of these related results are applicable in our setting, which fixes an exact load for every bin and minimizes the maximum number of fragments per bin, rather than the number of bins or the makespan.

1.1

Formal Problem Definition and Our Contribution

We study the following fundamental load-balancing problem introduced in [KFAS14] by Kobert et al. Load Balancing with Item Fragmentation (LBIF) Input: A multiset S = {𝑠1 , 𝑠2 , . . . , 𝑠 𝑁 }, with 𝑠𝑖 ∈ N, for all 1 ≤ 𝑖 ≤ 𝑁, and an integer 𝐵 > 0. 𝑁 ×𝐵 subject to: Output: The minimum value of max1≤ 𝑗 ≤ 𝐵 |{𝑖 : 𝑥𝑖, 𝑗 > 0}| over all matrices 𝑋 = (𝑥 𝑖, 𝑗 ) ∈ N ≥0 1.

Í𝐵

2.

Í𝑁

𝑗=1 𝑥 𝑖, 𝑗 = 𝑠𝑖 , for all 1 ≤ 𝑖 ≤ 𝑁.

𝑖=1 𝑥 𝑖, 𝑗 ∈ {⌊𝑊/𝐵⌋, ⌈𝑊/𝐵⌉}, for all 1 ≤ 𝑗 ≤ 𝐵, where 𝑊 =

We refer to the integers respectively.

Í𝑁

𝑖=1 𝑠𝑖 .

Í𝑁

𝑖=1 𝑥 𝑖, 𝑗 and max1≤ 𝑗 ≤ 𝐵 |{𝑖 : 𝑥 𝑖, 𝑗 > 0}| as the load and the combinatorial load,

Items S = {5, 5}

Bins (load ∈ {⌊𝑊/𝐵⌋, ⌈𝑊/𝐵⌉} = {3, 4})

⌈𝑊/𝐵⌉ = 4 ⌊𝑊/𝐵⌋ = 3 fragment

𝑠1 =5 𝑠2 =5

1

& pack

4 3 2 1 item 2 items 1 item

Figure 1: A simple example of an LBIF instance with 𝑁 = 2 items and 𝐵 = 3 bins and a solution with optimal combinatorial load 2: bin 2 contains fragments of both items. To explain the LBIF problem informally and to streamline the presentation, we associate each element of the multiset S with an item and the integer 𝐵 with the number of available bins. We are given 𝑁 items of strictly 3

positive integer size with total size 𝑊. We must assign the items to 𝐵 bins, where items may be fragmented across bins. Each bin must receive a load of either ⌊𝑊/𝐵⌋ or ⌈𝑊/𝐵⌉, ensuring that the loads of any two bins differ by at most one unit. Under this balancing constraint, the objective is to minimize the maximum number of item fragments placed into any single bin. See Figure 1 for an example. For simplicity of presentation, we use 𝑠𝑖 both for the item index 𝑖 and for its size if the meaning is clear from context. Otherwise, we use the index 𝑖 explicitly to avoid confusion. The following results are known for LBIF. Theorem 1.1 (Kobert et al. [KFAS14]). LBIF is NP-hard. Theorem 1.2 (Kobert et al. [KFAS14]). There exists an (OPT + 1)-approximation algorithm for LBIF that runs in O (𝑁 log 𝑁 + 𝐵) time. From a theory standpoint, one would like a strongly polynomial-time approximation algorithm for LBIF. When 𝐵 = 𝑁 O (1) , the O (𝑁 log 𝑁 + 𝐵)-time (OPT + 1)-approximation algorithm of Kobert et al. [KFAS14] runs in polynomial 𝑁 O (1) time. In particular, when 𝐵 ≤ 𝑁 log 𝑁, their algorithm runs in O (𝑁 log 𝑁) time. We are thus motivated to study the regime 𝐵 ≥ 𝑁. We denote the set of LBIF instances with 𝐵 ≥ 𝑁 by LBIF 𝑁 ≤ 𝐵 . Our central contribution is an exact algorithm for LBIF 𝑁 ≤ 𝐵 that runs in the optimal O (𝑁) time. Such a solution always has a combinatorial load of at most 2. Theorem 1.3. There exists an algorithm for LBIF 𝑁 ≤ 𝐵 that runs in O (𝑁) time and always returns an exact solution with combinatorial load at most 2. In particular, the assignment is output in a representation using O (𝑁) space. Proving Theorem 1.3 will be the focus of this paper. Combined with Theorem 1.2, Theorem 1.3 yields a strongly polynomial-time approximation algorithm for LBIF. Corollary 1.4. There exists an (OPT + 1)-approximation algorithm for LBIF that runs in O (𝑁 log 𝑁) time. Proof. After reading the 𝑁 item sizes, we compare 𝑁 with 𝐵 in O (1) time and run exactly one of the following two algorithms on the unchanged input. When 𝐵 < 𝑁, apply Theorem 1.2; its running time O (𝑁 log 𝑁 + 𝐵) is O (𝑁 log 𝑁) because 𝐵 < 𝑁. When 𝐵 ≥ 𝑁, apply Theorem 1.3; it returns an optimal assignment, which is in particular an (OPT + 1)-approximation, in O (𝑁) time. The result follows. □

1.2

Paper Organization and Overview of the Algorithm

We prove Theorem 1.3 by designing and analyzing an algorithm to solve LBIF 𝑁 ≤ 𝐵 in O (𝑁) time and space. The overall algorithm works in several phases, each described as a simple algorithm. First, we check whether a solution with OPT = 1 exists. If so, we construct such an assignment. The characterization and algorithm for this case are deferred to Section 3. If no OPT = 1 solution exists, we apply the algorithm presented in Section 2. This algorithm is guaranteed to produce a solution with OPT ≤ 2. Running these two phases in sequence guarantees an optimal solution. Section 4 concludes the paper with some final remarks. For the remainder of this paper, we assume ⌈𝑊/𝐵⌉ > 1. The special case ⌈𝑊/𝐵⌉ = 1 is trivial to solve by simply assigning one element of size 1 to a total of 𝑊 bins.

2

Combinatorial Load at Most Two

In this section, we present an algorithm that always (i.e., for any input instance of LBIF 𝑁 ≤ 𝐵 ) produces an assignment with combinatorial load at most 2. We first present the algorithm in Section 2.1 and analyze the behavior in Section 2.2. Let ℓ := ⌈𝑊/𝐵⌉ be the average target load per bin rounded up. By simple calculation, 𝑡 = 𝑊 − 𝐵(ℓ − 1) ∈ {1, . . . , 𝐵} is then the number of bins requiring target load ℓ. Indeed, since ℓ = ⌈𝑊/𝐵⌉, we have ℓ − 1 < 𝑊/𝐵 ≤ ℓ, which implies 0 < 𝑊 − 𝐵(ℓ − 1) ≤ 𝐵, so 𝑡 ∈ {1, . . . , 𝐵}. The multiset of strictly positive integers S = {𝑠1 , 𝑠2 , . . . , 𝑠 𝑁 } initially consists of the sizes of the items to be assigned. During the algorithm, we assign items or fragments of items from S to bins and update each 𝑠𝑖 to always represent the size of the fragment of item 𝑖 that is still to be assigned. To facilitate the exposition, we define similarly C = {𝑐 1 , 𝑐 2 , . . . , 𝑐 𝐵 } as 4

the multiset of 𝐵 target bin loads. We remove elements from C once their corresponding bins are completely filled. We write Cℓ −1 and Cℓ for the multisets consisting of elements in C with value (ℓ − 1) and ℓ, respectively. Elements of Cℓ −1 and elements of Cℓ are called (ℓ − 1)-bins and ℓ-bins, respectively. In the algorithm, we only keep track of their cardinalities |Cℓ −1 | = 𝐵 − 𝑡 and |Cℓ | = 𝑡 = 𝑊 − 𝐵(ℓ − 1), respectively. Therefore, updating these numbers is easily done with constant overhead.

2.1

The Algorithm

Overview. The algorithm for constructing a solution with combinatorial load at most 2 is split into two parts. First, in Algorithm 1, we iterate over the items that are guaranteed to fill any bin completely, possibly filling more than one bin at a time. Afterwards, Algorithm 2 fills the remaining bins with fragments from at most two items. Full bins are removed from C, and S is updated on the fly by removing the fragments of the items used. Algorithm 1 is applied when |S| < |C|, whereas Algorithm 2 is applied when |S| = |C|. We will show that we run Algorithm 1 until |S| = |C|, and from then on only run Algorithm 2. Inside the algorithms, we maintain a partition of S into Ssmall = {𝑠 ∈ S : 𝑠 ≤ ℓ − 1} and Slarge = {𝑠 ∈ S : 𝑠 ≥ ℓ}. The latter is the multiset of items that can each fill any bin completely. Since all sizes are integers, every item belongs to exactly one of the two multisets; in particular, an item of size exactly ℓ − 1 is small, even though it can fill an (ℓ − 1)-bin on its own. The multisets S, C, Ssmall , and Slarge will be updated in O (1) time as item fragments are consumed and produced. We assume that values reaching zero are automatically removed from these multisets. The formal problem definition represents an assignment by a matrix 𝑋 = (𝑥𝑖, 𝑗 ). In the algorithms, we encode this matrix as a collection of records, also denoted by 𝑋. Each record is a quadruple (𝑖, 𝑘, 𝑠, 𝑗), where 𝑘 denotes the number of fragments of size 𝑠 from the item with index 𝑖, and 𝑗 is either a bin index or the symbol ⊥. If 𝑗 is a bin index, then 𝑘 = 1, and the record assigns one fragment of size 𝑠 from item 𝑖 to bin 𝑗. The fragment need not fill the bin by itself. If several records have the same bin index 𝑗, their fragments are assigned to the same bin, and their sizes together equal its target load. If 𝑗 = ⊥, the record represents a batch of 𝑘 fragments of size 𝑠 from item 𝑖. Each fragment is placed in a distinct empty bin whose target load is 𝑠, such that each of these bins is filled by a single fragment. The record assigns a total size of 𝑘 · 𝑠 from item 𝑖. If 𝑠𝑖 > 𝑘 · 𝑠, the remaining size 𝑠𝑖 − 𝑘 · 𝑠 stays in S. The bin indices are omitted because bins with the same target load are interchangeable. Every record stored in 𝑋 has 𝑘 ≥ 1. If the algorithm computes a multiplicity of zero, no record is added. Algorithm 1 uses only records with 𝑗 = ⊥, whereas Algorithm 2 uses explicit bin indices to indicate which fragments are placed together. 2.1.1

The Case |S| < |C|: Filling Empty Bins with Large Items

To keep the running time bounded by O (𝑁) rather than O (𝐵), each iteration of the while loop in Algorithm 1 processes one large item. In that iteration, the item may be divided into fragments that fill several bins. Rather than recording a separate assignment for every bin, the algorithm adds at most two records to 𝑋: one representing all (ℓ − 1)-bins filled from the selected item and one representing all ℓ-bins filled from it. In each iteration, Algorithm 1 selects an item from Slarge . It first fills as many (ℓ − 1)-bins as possible. Once no such bins remain, it proceeds to fill the ℓ-bins. Concretely, Step 1 assigns 𝑎 𝑖 fragments of size ℓ − 1 of item 𝑖 to as many (ℓ − 1)-bins, and Step 2 then assigns 𝑏 𝑖 fragments of size ℓ of the residual item to as many ℓ-bins, where

𝑎 𝑖 = min ⌊𝑠𝑖 /(ℓ − 1)⌋, |Cℓ −1 |, |C| − |S| , 𝑏 𝑖 = min ⌊𝑠𝑖 /ℓ⌋, |Cℓ |, |C| − |S| , and 𝑠𝑖 , C, and S in the definition of 𝑏 𝑖 refer to the values after Step 1. The first term in each of the definitions of 𝑎 𝑖 and 𝑏 𝑖 limits the assignment according to the remaining size of item 𝑖. The second limits it according to the number of available bins of the relevant target load. The third, |C| − |S|, prevents the number of remaining bins from falling below the number of remaining items. Each positive value 𝑎 𝑖 or 𝑏 𝑖 is stored in a single record, irrespective of how many bins it represents. As we will argue in Observation 2.3, an item in Slarge is available as long as |S| < |C|. Hence, each iteration fills at least one bin and removes at most one item. The algorithm continues until |S| = |C|, at which point Algorithm 2 is applied to the remaining items and bins, together with the partial assignment 𝑋.

5

Input: S = Ssmall ∪ Slarge , bin target loads C = Cℓ −1 ∪ Cℓ , target load ℓ > 1 𝑋←∅ while |S| < |C| do Pick an item 𝑠𝑖 ∈ Slarge ▶ Step 1: fill entirely as many empty (ℓ−1)-bins as possible
𝑎 𝑖 ← min ⌊𝑠𝑖 /(ℓ − 1)⌋, |Cℓ −1 |, |C| − |S|  𝑋 ← 𝑋 ∪ (𝑖, 𝑎 𝑖 , ℓ − 1, ⊥) : 𝑎 𝑖 ≠ 0 // 𝑎 𝑖 (ℓ−1)-fragments of 𝑠𝑖 into distinct (ℓ−1)-bins 𝑠𝑖 ← 𝑠𝑖 − 𝑎 𝑖 (ℓ − 1); remove 𝑎 𝑖 bins from Cℓ −1 if 𝑠𝑖 = 0 then remove 𝑠𝑖 from S else reclassify 𝑠𝑖 into Ssmall or Slarge ▶ Step 2: fill entirely as many empty ℓ-bins as possible
𝑏 𝑖 ← min ⌊𝑠𝑖 /ℓ⌋, |Cℓ |, |C| − |S|  𝑋 ← 𝑋 ∪ (𝑖, 𝑏 𝑖 , ℓ, ⊥) : 𝑏 𝑖 ≠ 0 // 𝑏 𝑖 ℓ-fragments of 𝑠𝑖 into distinct ℓ-bins 𝑠𝑖 ← 𝑠𝑖 − 𝑏 𝑖 · ℓ; remove 𝑏 𝑖 bins from Cℓ if 𝑠𝑖 = 0 then remove 𝑠𝑖 from S else reclassify 𝑠𝑖 into Ssmall or Slarge end return 𝑋 Algorithm 1: The case |S| < |C|: fill empty bins with whole fragments of a large item. 2.1.2

The Case |S| = |C|: Filling a Bin with One Small Item and (a Fragment of) One Large Item

Once we have reached the point where |S| = |C|, we continue to fill the bins one by one. In broad terms, in each iteration of Algorithm 2, exactly one bin and one item in Ssmall will be removed by filling the bin with the item in Ssmall complemented (if required) with a fragment of an item in Slarge . More precisely, an iteration picks any 𝑠small ∈ Ssmall , any 𝑠large ∈ Slarge , and any remaining bin with target load 𝑐 𝑗 , places 𝑠small into bin 𝑗, and fills the residual capacity 𝑅 := 𝑐 𝑗 − 𝑠small with a fragment of size 𝑅 of 𝑠large . Once Ssmall or Slarge are empty, we can continue with a simple matching of items to bins (Observation 2.4). By this process, we can ensure that at most two items are assigned to any bin. Notably, while 𝑠small is fully assigned and removed and 𝑐 𝑗 is fully filled and removed in Algorithm 2, the item 𝑠large will never be fully removed in Step 3. Thus, |S| = |C| is maintained.

2.2

Analysis

We will now show that Algorithm 1 and Algorithm 2 together do in fact compute a solution to any instance of LBIF with |S| ≤ |C| with combinatorial load of at most 2. The heart of our correctness proof is to show that the following invariants are maintained at every step: Invariant 1. Before and after every iteration of Algorithms 1 and 2, ∑︁ ∑︁ 𝑠𝑖 = 𝑐𝑗.

(1)

𝑐𝑗 ∈ C

𝑠𝑖 ∈ S

Invariant 2. Before and after every iteration of Algorithms 1 and 2, |S| ≤ |C|.

(2)

Lemma 2.1. Invariants 1 and 2 hold before the start of the algorithm. Í Í Proof. By the definition of 𝐵 = |C|, 𝑡, and ℓ, we have 𝑐 𝑗 ∈ C 𝑐 𝑗 = 𝑡ℓ+(𝐵−𝑡) (ℓ−1) = 𝐵(ℓ−1)+𝑡 = 𝑊 = 𝑠𝑖 ∈ S 𝑠𝑖 , so Invariant 1 holds initially. By the definition of the problem, Invariant 2 also holds initially. □ Lemma 2.2. Algorithm 1 preserves Invariants 1 and 2. Proof. Invariant 1: Step 1 removes 𝑎 𝑖 bins of target load (ℓ − 1) and reduces 𝑠𝑖 by 𝑎 𝑖 (ℓ − 1). Step 2 removes 𝑏 𝑖 bins of target load ℓ and reduces 𝑠𝑖 by 𝑏 𝑖 · ℓ. In both steps, the total remaining item size and the total 6

Input: S = Ssmall ∪ Slarge , target loads C with |S| = |C|, target load ℓ > 1, partial assignment 𝑋 while Ssmall ≠ ∅ and Slarge ≠ ∅ do ▶ Step 1: pick a small item, a large item, and a bin Pick any 𝑠small ∈ Ssmall with index 𝑖 small , any 𝑠large ∈ Slarge with index 𝑖 large , and any 𝑐 𝑗 ∈ C 𝑅 ← 𝑐 𝑗 − 𝑠small // 0 ≤ 𝑅 ≤ ℓ − 1 < 𝑠large ▶ Step 2: pack bin 𝑗 with 𝑠small and an 𝑅-fragment of 𝑠large   𝑋 ← 𝑋 ∪ (𝑖 small , 1, 𝑠small , 𝑗) ∪ (𝑖 large , 1, 𝑅, 𝑗) : 𝑅 ≠ 0 Remove 𝑐 𝑗 from C; remove 𝑠small from S ▶ Step 3: update the residual large item Replace 𝑠large by (𝑠large − 𝑅) in S Reclassify the residual into Ssmall or Slarge end while S ≠ ∅ do ▶ Step 4: once Ssmall or Slarge is empty, match the elements exactly Pick any 𝑠𝑖 ∈ S with index 𝑖, and any 𝑐 𝑗 ∈ C  𝑋 ← 𝑋 ∪ (𝑖, 1, 𝑠𝑖 , 𝑗) // exact-fit deposits Remove 𝑐 𝑗 from C; remove 𝑠𝑖 from S end return 𝑋 Algorithm 2: The case |S| = |C|: fill each bin with one small item and possibly part of one large item. remaining target load decrease by the same amount, preserving Invariant 1. Invariant 2: The factor |C| − |S| in the calculation of 𝑎 𝑖 and 𝑏 𝑖 in Algorithm 1 ensures that the case |S| > |C| cannot occur. Thus, Invariant 2 is preserved. □ With the following observation, we can see that Algorithm 1 must terminate with |S| = |C|. That is, while |S| < |C|, there must be an element 𝑠 ∈ Slarge causing another iteration of Algorithm 1. Observation 2.3. While |S| < |C|, Slarge ≠ ∅. Proof. Assume Slarge = ∅. Then every 𝑠 ∈ S satisfies 𝑠 ≤ ℓ − 1. Thus, since |S| < |C|, ∑︁ ∑︁ 𝑠 ≤ |S|(ℓ − 1) < |C|(ℓ − 1) ≤ 𝑐 𝑗, 𝑐𝑗 ∈ C

𝑠∈ S

which contradicts Invariant 1. Hence, Slarge ≠ ∅.

□

The following observation justifies the use of Step 4 in Algorithm 2. Observation 2.4. While Invariant 1 holds, |S| = |C|, and either Ssmall = ∅ or Slarge = ∅, then S = C and 𝑠 = 𝑐 for any pair of 𝑠 ∈ S, 𝑐 ∈ C. Proof. Assume Ssmall = ∅. We will show by contradiction that 𝑠 = ℓ for any 𝑠 ∈ Slarge . Assume there exists an 𝑠 ∈ Slarge with 𝑠 > ℓ. We obtain ∑︁ ∑︁ 𝑠 > |S| · ℓ = |C| · ℓ ≥ 𝑐, 𝑐∈ C

𝑠∈ S

which contradicts Invariant 1. Thus, 𝑠 = ℓ for all 𝑠 ∈ Slarge . Now assume there exists a 𝑐 ∈ C with size 𝑐 ≠ ℓ. That is, 𝑐 = ℓ − 1. We obtain ∑︁ ∑︁ 𝑠 = |S| · ℓ = |C| · ℓ > 𝑐, 𝑐∈ C

𝑠∈ S

which again contradicts Invariant 1, proving our observation for the case Ssmall = ∅. The argument for Slarge = ∅ is analogous. □

7

We use Observation 2.4 to prove the validity of the invariants for Algorithm 2 in the following lemma. Lemma 2.5. Algorithm 2 preserves Invariants 1 and 2. Proof. Invariant 1: Steps 2 and 3 of Algorithm 2 remove a bin of target load 𝑐 𝑗 from C, and item fragments of total size 𝑠small + 𝑅 = 𝑠small + 𝑐 𝑗 − 𝑠small = 𝑐 𝑗 from S. Thus, each iteration of the first while loop removes equal total values from C and S, preserving Invariant 1. Consequently, the invariant holds upon termination of the first while loop. By Observation 2.4, the first execution of Step 4 therefore removes identical values from C and S, preserving Invariant 1. The same reasoning applies inductively to every subsequent execution of Step 4. Invariant 2: Step 2 removes one item from S and one bin from C. The item 𝑖large will not be removed, as for the remaining size, (𝑠large − 𝑅), we have: (𝑠large − 𝑅) = 𝑠large − 𝑐 𝑗 + 𝑠small ≥ ℓ − ℓ + 1 = 1. Step 4 trivially removes one item and one bin per iteration. Thus, Invariant 2 is preserved in either case. □ We observe that once we switch from Algorithm 1 to Algorithm 2, we will remain in Algorithm 2 until the end as in each iteration of Algorithm 2, we either solve the problem completely or remove exactly one element from S and one from C. Lemma 2.6. Algorithm 1 and Algorithm 2 terminate with a valid assignment. Proof. This follows directly from the invariants, Observations 2.3 and 2.4 and from the fact that, in every iteration, at least one bin is completely filled. □ Lemma 2.7. In Algorithm 1 and Algorithm 2, any bin is filled with at most 2 item fragments in total. Proof. Each bin is always assigned only one item (in Algorithm 1 or Step 4 of Algorithm 2) or one small item and part of one large item (in Step 2 of Algorithm 2). □ Lemma 2.8. For any LBIF 𝑁 ≤ 𝐵 and ℓ > 1, Algorithm 1 and Algorithm 2 construct an assignment with combinatorial load at most 2 in O (𝑁) time using O (𝑁) space. Proof. The overarching algorithm consists of two phases: Algorithm 1 (while |S| < |C|) and Algorithm 2 (once |S| = |C|). All operations in both phases trivially take O (1) time. In each iteration of Algorithm 1, the cardinality of Slarge is reduced by one or the algorithm terminates. Thus Algorithm 1, goes through at most |Slarge | iterations. In Algorithm 2, in each iteration of either loop, the cardinality of S is reduced by one. Thus, the total number of iterations in Algorithm 1 and Algorithm 2 together is bounded by |Slarge | + 𝑁 ≤ 2𝑁, yielding O (𝑁) total time. The only non-constant space requirement comes from the assignment 𝑋. Since at most two quadruples are added to 𝑋 during any iteration of either algorithm, and as argued before, the overall algorithm has O (𝑁) iterations, the algorithm uses O (𝑁) space. The validity of the resulting assignment from the entire algorithm and its combinatorial load follow from Lemmas 2.6 and 2.7. □

3

Combinatorial Load Exactly One

In the previous section, we presented an algorithm that finds an assignment with combinatorial load at most 2, for any LBIF 𝑁 ≤ 𝐵 instance. This is sufficient for Corollary 1.4, i.e., providing a strongly polynomial-time (OPT + 1)-approximation algorithm for LBIF (regardless of 𝑁 and 𝐵). However, our ultimate goal is Theorem 1.3: an exact algorithm for LBIF 𝑁 ≤ 𝐵 . Since Section 2 focused on providing an assignment with combinatorial load at most 2, all that remains is to provide a method for detecting whether an assignment with combinatorial load exactly 1 exists, and if so, constructing one. Recall the notation ℓ := ⌈𝑊/𝐵⌉ for the target load rounded up and 𝑡 := 𝑊 − 𝐵(ℓ − 1) for the number of bins with target load ℓ. As before, the trivial case ℓ ≤ 1 is omitted. The following observation is crucial for the design of our algorithm.

8

Observation 3.1. For any LBIF 𝑁 ≤ 𝐵 instance with OPT = 1, the size 𝑠𝑖 of each item must be representable as 𝑠𝑖 = 𝑘 𝑖 ℓ + ℎ𝑖 (ℓ − 1), where 𝑘 𝑖 , ℎ𝑖 ∈ N ≥0 are the number of bins of target load ℓ and (ℓ − 1) filled by fragments from 𝑠𝑖 , respectively. Furthermore, the number ℎ𝑖 of (ℓ − 1)-fragments must be of the form ℎ 𝑖 = ℓ · 𝑚 𝑖 + 𝑓𝑖 ,

where 𝑓𝑖 := (−𝑠𝑖 ) mod ℓ,

for some integer 𝑚 𝑖 ∈ N ≥0 . Proof. The first part, 𝑠𝑖 = 𝑘 𝑖 ℓ + ℎ𝑖 (ℓ − 1), is trivial, as for any assignment with combinatorial load 1, any item must be assigned exactly to a combination of bins (each with target load (ℓ − 1) or ℓ). For the second part of the observation, broadly speaking, the argument boils down to the fact that after assigning all (ℓ − 1)-sized fragments of 𝑠𝑖 to bins of target load (ℓ − 1), any remainder of 𝑠𝑖 , though possibly a remainder of 0, must be divisible by ℓ in order to fill up bins with target load ℓ exactly. Let us first consider the minimal number of (ℓ − 1)-sized fragments an item 𝑠𝑖 must contain in its decomposition into fragments such that the item size is divisible by ℓ; i.e., the smallest number 𝑓𝑖 such that (𝑠𝑖 − 𝑓𝑖 (ℓ − 1)) mod ℓ = 0. Choosing 𝑓𝑖 = (−𝑠𝑖 ) mod ℓ, we obtain: (𝑠𝑖 − 𝑓𝑖 (ℓ − 1)) mod ℓ = (𝑠𝑖 − ((−𝑠𝑖 ) mod ℓ) (ℓ − 1)) mod ℓ = (𝑠𝑖 − ℓ((−𝑠𝑖 ) mod ℓ) + ((−𝑠𝑖 ) mod ℓ)) mod ℓ = (𝑠𝑖 + ((−𝑠𝑖 ) mod ℓ)) mod ℓ = (𝑠𝑖 − 𝑠𝑖 ) mod ℓ = 0 By the definition of 𝑓𝑖 , we have 0 ≤ 𝑓𝑖 < ℓ. Thus, 𝑓𝑖 = (−𝑠𝑖 ) mod ℓ is the smallest non-negative number that satisfies (𝑠𝑖 − 𝑓𝑖 (ℓ − 1)) mod ℓ = 0. For the term ℓ · 𝑚 𝑖 , we analyze the remaining item size after 𝑓𝑖 fragments of size (ℓ − 1) have been assigned to as many (ℓ − 1)-bins and removed. Let the remaining size to be distributed from item 𝑠𝑖 be denoted by 𝑟 𝑖 . That is, 𝑟 𝑖 = 𝑠𝑖 − 𝑓𝑖 (ℓ − 1) = 𝑘 𝑖 ℓ + ℎ𝑖 (ℓ − 1) − 𝑓𝑖 (ℓ − 1) = 𝑘 𝑖 ℓ + 𝑔𝑖 (ℓ − 1), where 𝑔𝑖 = ℎ𝑖 − 𝑓𝑖 . By the argument above, 𝑟 𝑖 mod ℓ = 0. Trivially, 𝑘 𝑖 ℓ mod ℓ = 0. Hence, 𝑔𝑖 (ℓ − 1) mod ℓ = 0 must hold as well. Since (ℓ − 1) and ℓ are coprime and thus, do not share a prime factor, it must be that 𝑔𝑖 mod ℓ = 0 for any OPT = 1 solution and can thus be written in the form 𝑔𝑖 = ℓ · 𝑚 𝑖 . □ Based on Observation 3.1, we describe an algorithm (see Algorithm 3 for pseudocode) that detects whether OPT = 1 and, if so, produces such an assignment. The algorithm proceeds in three steps, which we detail next. It uses the following quantities. For each item 𝑖, 𝑓𝑖 = (−𝑠𝑖 ) mod ℓ is the number of forced fragments of size ℓ − 1 Í𝑁 from Observation 3.1, and 𝐹 := 𝑖=1 𝑓𝑖 is their total number. The counter 𝑟 is the number of (ℓ − 1)-bins that are still empty after the forced fragments have been placed; initially, 𝑟 = 𝐵 − 𝑡 − 𝐹. Finally, 𝑛𝑖 is the number of blocks of ℓ fragments of size ℓ − 1 each that Step 2 takes from item 𝑖; it plays the role of 𝑚 𝑖 in Observation 3.1. Step 1 iterates over all items 𝑠𝑖 in S, computing 𝑓𝑖 . If 𝑠𝑖 < 𝑓𝑖 (ℓ − 1), the algorithm correctly returns Fail. If 𝑠𝑖 ≥ 𝑓𝑖 (ℓ − 1), we assign these 𝑓𝑖 fragments to 𝑓𝑖 empty bins of target load (ℓ − 1), each fragment filling one bin entirely. We deduct 𝑓𝑖 (ℓ − 1) from 𝑠𝑖 . By construction, the updated size 𝑠𝑖 is now non-negative and divisible by ℓ. Í The algorithm computes the total number 𝐹 = 𝑠𝑖 ∈ S 𝑓𝑖 . Recall that 𝐵 − 𝑡 is the number of available bins with target load (ℓ − 1). If 𝐹 > 𝐵 − 𝑡, a valid OPT = 1 packing is impossible, and the algorithm correctly returns Fail. Otherwise, after depositing the 𝐹 forced fragments, 𝐵 − 𝑡 − 𝐹 empty bins of target load (ℓ − 1) remain. By Observation 3.1, any additional fragments of size (ℓ − 1) extracted from an item must be extracted in blocks of ℓ fragments in order to preserve the item’s divisibility by ℓ. Let us call such blocks full blocks. Therefore, the total number of remaining (ℓ − 1)-bins across the entire instance must be a multiple of ℓ. If it is not, the algorithm correctly returns Fail. If it is, then we proceed to Step 2. Step 2 greedily fills the remaining 𝑟 = 𝐵 − 𝑡 − 𝐹 bins with target load (ℓ − 1) using full blocks. As verified, 𝑟 is a multiple of ℓ. The algorithm iterates through the remaining available items. The loop terminates early when all (ℓ − 1)-bins are filled. We compute the number 𝑛𝑖 of full blocks that can be extracted from the remaining item size 𝑠𝑖 , i.e., after having extracted the 𝑓𝑖 fragments of size (ℓ − 1). Since each full block has total size ℓ(ℓ − 1), no more than 9

Input: S = {𝑠1 , . . . , 𝑠 𝑁 }, bin target loads C, target load ℓ > 1 𝑋←∅ ▶ Step 1: forced (ℓ−1)-fragments foreach 𝑠𝑖 ∈ S do 𝑓𝑖 ← (−𝑠𝑖 ) mod ℓ if 𝑠𝑖 < 𝑓𝑖 (ℓ − 1) then return Fail 𝑋 ← 𝑋 ∪ {(𝑖, 𝑓𝑖 , ℓ − 1, ⊥) : 𝑓𝑖 > 0} // 𝑓𝑖 (ℓ − 1)-fragments of 𝑠𝑖 into distinct (ℓ − 1)-bins 𝑠𝑖 ← 𝑠𝑖 − 𝑓𝑖 (ℓ − 1) end Í 𝐹 ← 𝑖 𝑓𝑖 if 𝐹 > 𝐵 − 𝑡 then return Fail if (𝐵 − 𝑡 − 𝐹) mod ℓ ≠ 0 then return Fail ▶ Step 2: bulk-fill remaining (ℓ−1)-bins in blocks of ℓ fragments 𝑟 ← 𝐵−𝑡−𝐹 foreach 𝑠𝑖 ∈ S with 𝑠𝑖 ≥ ℓ(ℓ − 1) while 𝑟 > 0 do
𝑛𝑖 ← min ⌊𝑠𝑖 /(ℓ (ℓ − 1))⌋, 𝑟/ℓ 𝑋 ← 𝑋 ∪ {(𝑖, 𝑛𝑖 · ℓ, ℓ − 1, ⊥) : 𝑛𝑖 > 0} // 𝑛𝑖 · ℓ (ℓ − 1)-fragments of 𝑠𝑖 into distinct (ℓ−1)-bins 𝑠𝑖 ← 𝑠𝑖 − 𝑛𝑖 ℓ (ℓ − 1) 𝑟 ← 𝑟 − 𝑛𝑖 ℓ end if 𝑟 > 0 then return Fail ▶ Step 3: fill the ℓ-bins foreach 𝑠𝑖 ∈ S with 𝑠𝑖 > 0 do 𝑋 ← 𝑋 ∪ {(𝑖, 𝑠𝑖 /ℓ, ℓ, ⊥)} // (𝑠𝑖 /ℓ) ℓ-fragments of 𝑠𝑖 into distinct ℓ-bins end return 𝑋 Algorithm 3: Combinatorial load of 1: Test whether an assignment with combinatorial load 1 exists, and if so, construct such assignment by decomposing the items into 𝐵 − 𝑡 and 𝑡 = 𝑊 − 𝐵(ℓ − 1) fragments of size (ℓ − 1) and ℓ, resp. ⌊(𝑠𝑖 /(ℓ (ℓ − 1))⌋ blocks can be extracted from 𝑠𝑖 . Moreover, in Step 2 we only fill the 𝑟 as of yet remaining empty (ℓ − 1)-bins, and each block fills ℓ of them. Thus, no more than 𝑟/ℓ blocks are needed. Hence, 𝑛𝑖 ≤ 𝑟/ℓ. In each iteration with 𝑠𝑖 , we take the minimum of these two values as 𝑛𝑖 and extract exactly 𝑛𝑖 · ℓ fragments of size (ℓ − 1) from item 𝑠𝑖 . These are assigned to the available distinct (ℓ − 1)-bins. Then we deduct the deposited size from the item and decrease the number of remaining empty (ℓ − 1)-bins by the exact number of bins we just filled. After iterating through all items, if 𝑟 > 0, it means we exhausted all available item sizes but failed to fill all the (ℓ − 1)-bins, in which case the algorithm returns Fail. Otherwise, it proceeds to Step 3. In Step 3, all (ℓ − 1)-bins have already been filled. Furthermore, the remaining size of every item 𝑠𝑖 is guaranteed to be a multiple of ℓ. Therefore, it can be sliced into an exact integer number of ℓ-fragments, each of which we assign to a yet-empty ℓ-bin, thereby filling the 𝑡 bins with target load ℓ. Lemma 3.2. For any LBIF 𝑁 ≤ 𝐵 instance with ℓ > 1, Algorithm 3 checks whether OPT = 1 in O (𝑁) time. If OPT = 1, an assignment with this value is constructed in O (𝑁) time using O (𝑁) space. Proof. We first prove that Algorithm 3 returns a valid assignment with combinatorial load 1 if and only if such an assignment exists. (⇒) We show that the algorithm returns a valid OPT = 1 assignment. By construction, the algorithm assigns fragments of size (ℓ − 1) only to (ℓ − 1)-bins (Steps 1 and 2), and fragments of size ℓ only to ℓ-bins (Step 3). In Step 1, 𝑓𝑖 fragments are extracted from 𝑠𝑖 . The condition 𝑠𝑖 ≥ 𝑓𝑖 (ℓ − 1) guarantees that 𝑠𝑖 is large enough to extract all 𝑓𝑖 fragments from it. In Step 2, 𝑛𝑖 full blocks of 10

size ℓ(ℓ − 1) are extracted. The condition 𝑛𝑖 ≤ ⌊𝑠𝑖 /(ℓ(ℓ − 1))⌋ similarly guarantees that, after removing the 𝑓𝑖 forced fragments, 𝑠𝑖 is large enough to contain 𝑛𝑖 blocks. Thus, all fragment sizes are valid. Furthermore, because 𝑟 = 0 at the end of Step 2, all (𝐵 − 𝑡) bins of target load (ℓ − 1) are completely filled. At the start of Step 3, the remaining size 𝑠𝑖 of every item is divisible by ℓ because, after subtracting the 𝑓𝑖 forced fragments to make the remainder divisible by ℓ (Step 1), we have only subtracted multiples of ℓ (Step 2). Therefore, Step 3 partitions the remaining item sizes into fragments of size ℓ. Since the total size 𝑊 = 𝑡ℓ + (𝐵 − 𝑡) (ℓ − 1) is preserved and the (ℓ − 1)-bins are full, the remaining total item size fills the remaining 𝑡 bins of target load ℓ. Thus, the maximum combinatorial load is exactly 1. (⇐) If an OPT = 1 assignment exists, we must show the algorithm does not return Fail. By Observation 3.1, any valid OPT = 1 assignment must allocate exactly ℎ𝑖 = ℓ · 𝑚 𝑖 + 𝑓𝑖 fragments of size (ℓ − 1) from item 𝑠𝑖 . Therefore, every item 𝑠𝑖 must have a total size of at least 𝑓𝑖 (ℓ − 1); otherwise, no such assignment could exist. Consequently, the check 𝑠𝑖 < 𝑓𝑖 (ℓ − 1) in Step 1 will correctly pass. The total number Í of forced fragments of size (ℓ − 1), 𝐹 = 𝑓𝑖 , represents the minimum number of (ℓ − 1)-bins required. If 𝐹 > (𝐵 − 𝑡), no valid assignment can exist, so the algorithm passes this check. Furthermore, by Observation 3.1, the remaining (𝐵 − 𝑡 − 𝐹) bins of target load (ℓ − 1) must be filled in blocks of ℓ of them to preserve the divisibility by ℓ of the items. This implies that (𝐵 − 𝑡 − 𝐹) must be divisible by ℓ. Thus, the check (𝐵 − 𝑡 − 𝐹) mod ℓ ≠ 0 will also pass. In Step 2, because 𝑟 is a multiple of ℓ and OPT = 1 guarantees that the number of fragments of size (ℓ − 1) is sufficient to fill all remaining empty bins with target load (ℓ − 1), the full-block filling strategy fills all these bins. Thus, the algorithm will not fail in Step 2. Finally, we analyze the complexity. Each item is processed a constant number of times, and all arithmetic Í operations are constant-time. Clearly, the calculation of line 𝐹 ← 𝑖 𝑓𝑖 is dominated by the preceding loop. Therefore, the total running time is O (𝑁). The output assignment stores only one quadruple per deposited block, so it uses O (𝑁) space. □ The correctness of Algorithm 3 directly yields the following characterization. Corollary 3.3. For any LBIF 𝑁 ≤ 𝐵 instance, OPT = 1

⇔

∀𝑖 ∈ {1, . . . , 𝑁 }, 𝑠𝑖 ≥ ((−𝑠𝑖 ) mod ℓ) (ℓ − 1) 𝑁 ∑︁ and (−𝑠𝑖 ) mod ℓ ≤ 𝐵ℓ − 𝑊

and

and

𝑖=1 𝑁 ∑︁

𝑁 ∑︁ 𝑠𝑖 − ((−𝑠𝑖 ) mod ℓ) (ℓ − 1) ⌋ · ℓ ≥ 𝐵ℓ − 𝑊 − (−𝑠𝑖 ) mod ℓ ℓ(ℓ − 1) 𝑖=1 𝑖=1 ! 𝑁 ∑︁ 𝐵ℓ − 𝑊 − (−𝑠𝑖 ) mod ℓ mod ℓ = 0.

⌊

(3) (4)

(5)

(6)

𝑖=1

Here, 𝐵ℓ − 𝑊 = 𝐵 − 𝑡 is the number of (ℓ − 1)-bins. Lemmas 2.8 and 3.2 prove Theorem 1.3: we first run Algorithm 3 on a copy of the item sizes. If it returns an assignment, this assignment has combinatorial load 1 and is optimal. Otherwise, OPT ≥ 2 and we run Algorithm 1 followed by Algorithm 2 on the original item sizes, which by Lemma 2.8 yields combinatorial load at most 2, which is again optimal. Both phases take O (𝑁) time and space.

4

Concluding Remarks

The main contributions of this paper are twofold. From the results perspective, Theorem 1.3 and Corollary 1.4 improve on the widely used algorithm of Kobert et al. [KFAS14], and they may inspire improvements in other settings in parallel and distributed systems or in iterative algorithms that rebalance their workload at every step. In particular, Theorem 1.3 establishes that the otherwise NP-hard problem has a linear-time solution under assumptions that naturally arise in high-performance computing. Furthermore, the simplicity of the presented algorithm makes it readily applicable within existing scheduling frameworks. 11

From an educational perspective, our paper may serve as material for a class on mathematical optimization, showcasing a remarkably simple and optimal algorithm obtained through combinatorial insight. In particular, our algorithm makes no use of advanced data structures: it only uses standard arithmetic and set operations, making it especially suitable as teaching material since students can focus on the underlying ideas rather than on implementation details.

Declarations We used an LLM to produce the Ti𝑘Z code for Figure 1 based on a textual description we provided. Furthermore, LLMs generated feedback on the stylistic polishing of the final manuscript, which we then implemented ourselves where we thought it was useful. All technical content and ideas were developed and written by us, the human authors. We assume responsibility for all content.

References [ADHR04]

Gautam Altekar, Sandhya Dwarkadas, John P. Huelsenbeck, and Fredrik Ronquist. Parallel Metropolis coupled Markov chain Monte Carlo for Bayesian phylogenetic inference. Bioinformatics, 20(3):407–415, 02 2004. doi:10.1093/bioinformatics/btg427.

[AKS14]

Andre J. Aberer, Kassian Kobert, and Alexandros Stamatakis. ExaBayes: Massively parallel Bayesian tree inference for the whole-genome era. Molecular Biology and Evolution, 31(10):2553– 2556, 2014. doi:10.1093/molbev/msu236.

[BD97]

Jacek Blazewicz and Maciej Drozdowski. Distributed processing of divisible jobs with communication startup costs. Discret. Appl. Math., 76(1-3):21–41, 1997. doi:10.1016/S0166-218X(96) 00115-1.

[BGW19]

Luca Bertazzi, Bruce Golden, and Xingyin Wang. The bin packing problem with item fragmentation: A worst-case analysis. Discrete Applied Mathematics, 261:63–77, 2019. doi:10.1016/j.dam. 2018.08.023.

[BH07]

Luiz André Barroso and Urs Hölzle. The case for energy-proportional computing. Computer, 40(12):33–37, 2007. doi:10.1109/MC.2007.443.

[CC14]

Marco Casazza and Alberto Ceselli. Mathematical programming algorithms for bin packing problems with item fragmentation. Computers & Operations Research, 46:1–11, 2014. doi: 10.1016/j.cor.2013.12.008.

[CMSM+ 15] José R. Correa, Alberto Marchetti-Spaccamela, Jannik Matuschke, Leen Stougie, Ola Svensson, Víctor Verdugo, and José Verschae. Strong LP formulations for scheduling splittable jobs on unrelated machines. Mathematical Programming, 154:305–328, 2015. doi:10.1007/ s10107-014-0831-8. [Cyb89]

George Cybenko. Dynamic load balancing for distributed memory multiprocessors. Journal of Parallel and Distributed Computing, 7(2):279–301, 1989. doi:10.1016/0743-7315(89) 90021-X.

[DG08]

Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, 2008. doi:10.1145/1327452.1327492.

[DJ19]

Max A. Deppert and Klaus Jansen. Near-linear approximation algorithms for scheduling problems with batch setup times. In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019, pages 155–164. ACM, 2019. doi:10.1145/3323165.3323200.

[Eki21]

Ali Ekici. Bin packing problem with conflicts and item fragmentation. Computers & Operations Research, 126:105113, 2021. doi:10.1016/j.cor.2020.105113. 12

[Ev06]

Leah Epstein and Rob van Stee. Online scheduling of splittable tasks. ACM Transactions on Algorithms, 2(1):116–133, 2006. doi:10.1145/1125994.1125999.

[Fel81]

Joseph Felsenstein. Evolutionary trees from DNA sequences: a maximum likelihood approach. Journal of Molecular Evolution, 17(6):368–376, 1981. doi:10.1007/BF01734359.

[GARK11]

Benjamin Gufler, Nikolaus Augsten, Angelika Reiser, and Alfons Kemper. Handling data skew in mapreduce. In Frank Leymann, Ivan I. Ivanov, Marten van Sinderen, and Boris Shishkov, editors, CLOSER 2011 - Proceedings of the 1st International Conference on Cloud Computing and Services Science, Noordwijkerhout, Netherlands, 7-9 May, 2011, pages 574–583. SciTePress, 2011. doi:10.5220/0003391105740583.

[Gra66]

Ronald L. Graham. Bounds for certain multiprocessing anomalies. Bell System Tech. J., 45:1563– 1581, 1966. URL: https://fanchung.ucsd.edu/ron/papers/66_04_multiprocessing. pdf.

[Gra69]

Ronald L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2):416–429, 1969. doi:10.1137/0117039.

[HKH+ 21]

Lukas Hübner, Alexey M. Kozlov, Demian Hespe, Peter Sanders, and Alexandros Stamatakis. Exploring parallel MPI fault tolerance mechanisms for phylogenetic inference with RAxML-NG. Bioinformatics, 37(22):4056–4063, 2021. doi:10.1093/bioinformatics/btab399.

[Kar72]

Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972. doi:10.1007/978-1-4684-2001-2\_9.

[KDF+ 19]

Alexey M. Kozlov, Diego Darriba, Tomáš Flouri, Benoit Morel, and Alexandros Stamatakis. RAxML-NG: a fast, scalable and user-friendly tool for maximum likelihood phylogenetic inference. Bioinformatics, 35(21):4453–4455, 2019. doi:10.1093/bioinformatics/btz305.

[KFAS14]

Kassian Kobert, Tomás Flouri, Andre J. Aberer, and Alexandros Stamatakis. The divisible load balance problem and its application to phylogenetic inference. In Dan Brown and Burkhard Morgenstern, editors, Algorithms in Bioinformatics - 14th International Workshop, WABI 2014, Wroclaw, Poland, September 8-10, 2014. Proceedings, Lecture Notes in Computer Science, pages 204–216. Springer, 2014. doi:10.1007/978-3-662-44753-6\_16.

[KK98]

George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1):359–392, 1998. doi:10.1137/ S1064827595287997.

[KSF17]

Kassian Kobert, Alexandros Stamatakis, and Tomáš Flouri. Efficient detection of repeating sites to accelerate phylogenetic likelihood calculations. Systematic Biology, 66(2):205–217, 2017. doi:10.1093/sysbio/syw075.

[KSV03]

Piotr Krysta, Peter Sanders, and Berthold Vöcking. Scheduling and traffic allocation for tasks with bounded splittability. In Branislav Rovan and Peter Vojtás, editors, Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings, volume 2747 of Lecture Notes in Computer Science, pages 500–510. Springer, 2003. doi:10.1007/978-3-540-45138-9\_44.

[KTR12]

Lars Kolb, Andreas Thor, and Erhard Rahm. Load balancing for mapreduce-based entity resolution. In Anastasios Kementsietsidis and Marcos Antonio Vaz Salles, editors, IEEE 28th International Conference on Data Engineering (ICDE 2012), Washington, DC, USA (Arlington, Virginia), 1-5 April, 2012, pages 618–629. IEEE Computer Society, 2012. doi:10.1109/ICDE.2012.22.

13

[KYT20]

Paschalia Kapli, Ziheng Yang, and Maximilian J. Telford. Phylogenetic tree building in the genomic age. Nature Reviews Genetics, 21(7):428–444, 2020. doi:10.1038/s41576-020-0233-0.

[LAP+ 14]

Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor-Yiing Su. Scaling distributed machine learning with the parameter server. In Jason Flinn and Hank Levy, editors, 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI ’14, Broomfield, CO, USA, October 6-8, 2014, pages 583–598. USENIX Association, 2014. URL: https://www.usenix.org/conference/ osdi14/technical-sessions/presentation/li_mu.

[LSS22]

Dimitrios Los, Thomas Sauerwald, and John Sylvester. Balanced allocations: Caching and packing, twinning and thinning. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1847–1874. SIAM, 2022. doi:10.1137/1.9781611977073. 74.

[McN59]

Robert McNaughton. Scheduling with deadlines and loss functions. Management Science, 6(1):1–12, 1959. URL: http://www.jstor.org/stable/2627472.

[MFS17]

Benoit Morel, Tomás Flouri, and Alexandros Stamatakis. A novel heuristic for data distribution in massively parallel phylogenetic inference using site repeats. In 19th IEEE International Conference on High Performance Computing and Communications; 15th IEEE International Conference on Smart City; 3rd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2017, Bangkok, Thailand, December 18-20, 2017, pages 81–88. IEEE Computer Society, 2017. doi:10.1109/HPCC-SMARTCITY-DSS.2017.11.

[MHH+ 22]

Dheevatsa Mudigere, Yuchen Hao, Jianyu Huang, Zhihao Jia, Andrew Tulloch, Srinivas Sridharan, Xing Liu, Mustafa Ozdal, Jade Nie, Jongsoo Park, Liang Luo, Jie Amy Yang, Leon Gao, Dmytro Ivchenko, Aarti Basant, Yuxi Hu, Jiyan Yang, Ehsan K. Ardestani, Xiaodong Wang, Rakesh Komuravelli, Ching-Hsiang Chu, Serhat Yilmaz, Huayu Li, Jiyuan Qian, Zhuobo Feng, Yinbin Ma, Junjie Yang, Ellie Wen, Hong Li, Lin Yang, Chonglin Sun, Whitney Zhao, Dimitry Melts, Krishna Dhulipala, K. R. Kishore, Tyler Graf, Assaf Eisenman, Kiran Kumar Matam, Adi Gangidi, Guoqiang Jerry Chen, Manoj Krishnan, Avinash Nayak, Krishnakumar Nair, Bharath Muthiah, Mahmoud khorashadi, Pallab Bhattacharya, Petr Lapukhov, Maxim Naumov, Ajit Mathews, Lin Qiao, Mikhail Smelyanskiy, Bill Jia, and Vijay Rao. Software-hardware co-design for fast and scalable training of deep learning recommendation models. In Valentina Salapura, Mohamed Zahran, Fred Chong, and Lingjia Tang, editors, ISCA ’22: The 49th Annual International Symposium on Computer Architecture, New York, New York, USA, June 18 - 22, 2022, pages 993–1011. ACM, 2022. doi:10.1145/3470496.3533727.

[MR01]

Nir Menakerman and Raphael Rom. Bin packing with item fragmentation. In Frank K. H. A. Dehne, Jörg-Rüdiger Sack, and Roberto Tamassia, editors, Algorithms and Data Structures, 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001, Proceedings, volume 2125 of Lecture Notes in Computer Science, pages 313–324. Springer, 2001. doi: 10.1007/3-540-44634-6\_29.

[SKFS16]

Constantin Scholl, Kassian Kobert, Tomáš Flouri, and Alexandros Stamatakis. The divisible load balance problem with shared cost and its application to phylogenetic inference. In 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 408–417. IEEE, 2016. doi:10.1109/IPDPSW.2016.38.

[ST19]

Shumpei Shiina and Kenjiro Taura. Almost deterministic work stealing. In Michela Taufer, Pavan Balaji, and Antonio J. Peña, editors, Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2019, Denver, Colorado, USA, November 17-19, 2019, pages 47:1–47:16. ACM, 2019. doi:10.1145/3295500.3356161.

14

[STY08]

Hadas Shachnai, Tami Tamir, and Omer Yehezkely. Approximation schemes for packing with item fragmentation. Theory Comput. Syst., 43(1):81–98, 2008. doi:10.1007/S00224-007-9082-X.

[SY07]

Hadas Shachnai and Omer Yehezkely. Fast asymptotic FPTAS for packing fragmentable items with costs. In Erzsébet Csuhaj-Varjú and Zoltán Ésik, editors, Fundamentals of Computation Theory, 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings, volume 4639 of Lecture Notes in Computer Science, pages 482–493. Springer, 2007. doi:10.1007/978-3-540-74240-1\_42.

[VGR03]

Bharadwaj Veeravalli, Debasish Ghose, and Thomas G. Robertazzi. Divisible load theory: A new paradigm for load scheduling in distributed systems. Clust. Comput., 6(1):7–17, 2003. doi:10.1023/A:1020958815308.

[WL08]

Dong Hyuk Woo and Hsien-Hsin S. Lee. Extending amdahl’s law for energy-efficient computing in the many-core era. Computer, 41(12):24–31, 2008. doi:10.1109/MC.2008.494.

15

Related documents

• Extremal Families for the Erdős--Kleitman Problem: The Missing Constructions#800116
• An In-depth Study of LLM Contributions to the Bin Packing Problem#288183
• The Minimum-Weight Mixed Dominating Set on Threshold Graphs#924639
• Near-Tight Theoretical Bounds for Incentive Compatibility in Bitcoin Mining#405539
• Packing Diverse Shortest Cycles#1234196