Balanced number partitioning

Balanced number partitioning is a variant of multiway number partitioning in which there are constraints on the number of items allocated to each set. The input to the problem is a set of n items of different sizes, and two integers m, k. The output is a partition of the items into m subsets, such that the number of items in each subset is at most k. Subject to this, it is required that the sums of sizes in the m subsets are as similar as possible.

An example application is identical-machines scheduling where each machine has a job-queue that can hold at most k jobs. The problem has applications also in manufacturing of VLSI chips, and in assigning tools to machines in flexible manufacturing systems.

In the standard three-field notation for optimal job scheduling problems, the problem of minimizing the largest sum is sometimes denoted by "P | # ≤ k | C_max". The middle field "# ≤ k" denotes that the number of jobs in each machine should be at most k. This is in contrast to the unconstrained version, which is denoted by " $P\parallel C_{\max }$ ".

Two-way balanced partitioning

A common special case called two-way balanced partitioning is when there should be two subsets (m = 2). The two subsets should contain floor(n/2) and ceiling(n/2) items. It is a variant of the partition problem. It is NP-hard to decide whether there exists a partition in which the sums in the two subsets are equal; see problem [SP12]. There are many algorithms that aim to find a balanced partition in which the sum is as nearly-equal as possible.

Coffman, Frederickson and Lueker present a restricted version of the LPT algorithm (called RLPT), in which inputs are assigned in pairs. When inputs are uniformly-distributed random variables, the expected largest sum of RLPT is exactly ${\frac {n}{4}}+{\frac {1}{2n+2}}$ . The expected work-difference (difference between largest and smallest sum) is $\Theta (1/n)$ .
Lueker presents a variant of the LDM algorithm (called the pairwise differencing method (PDM)). Its expected work-difference is $\Theta (1/n)$ .
Tsai presents an algorithm called Restricted Largest Difference (RLD). Its work-difference is $O(\log n/n^{2})$ almost surely.
Yakir presents a balanced variant of the LDM algorithm for m = 2, called BLDM. Its expected work-difference is $n^{-\Theta (\log n)}$ .
Mertens presents a complete anytime algorithm for balanced two-way partitioning. It combines the BLDM algorithm with the complete-Karmarkar–Karp algorithm.

Balanced triplet partitioning

Another special case called 3-partitioning is when the number of items in each subset should be at most 3 (k = 3). Deciding whether there exists such a partition with equal sums is exactly the 3-partition problem, which is known to be strongly NP-hard. There are approximation algorithms that aim to find a partition in which the sum is as nearly-equal as possible.

Kellerer and Woeginger adapt the LPT algorithm to triplet partitioning (where there are at most 3*m items, and each subset should contain at most 3 items). Their algorithm is called modified-LPT or MLPT. It orders the items from large to small, and puts each item in turn into the bin with the smallest sum among those bins that contain fewer than 3 items. They show that the MLPT algorithm attains at most ${\frac {4m-1}{3m}}$ of the minimum largest sum, which is the same approximation ratio that LPT attains for the unconstrained problem. The bound is tight for MLPT.
Chen, He and Lin show that, for the same problem, MLPT attains at least ${\frac {3m-1}{4m-2}}$ of the maximum smallest sum, which is again the same ratio that LPT attains for the unconstrained problem.
Kellerer and Kotov present a different algorithm (for the case with exactly 3*m items), that attains at most $7/6$ of the minimum largest sum.

Balanced partitioning with larger cardinalities

A more general case, called k-partitioning, is when the number of items in each subset should be at most k, where k can be any positive integer..

Babel, Kellerer and Kotov study a variant in which there are k×m items (for some integer k), and each of the m sets must contain exactly k items. They present several heuristic algorithms for approximating the minimum largest sum:
- Folding algorithm: optimal for m = 2, and in general has tight approximation ratio $2-{\frac {1}{m}}$ .
- Exchange algorithm: tight approximation ratio $2-{\frac {2}{m+1}}$ . It is not known if it runs in polynomial time.
- Primal-dual algorithm (a combination of LPT and MultiFit): approximation ratio at most $4/3$ . It is tight for k = 4 when m is sufficiently large; the precise lower bound is ${\frac {4m}{3m+1}}$ ).^: Thm.11
- The also conjecture that Modified-LPT has an approximation ratio ${\frac {4m-1}{3m}}$ . Currently, this conjecture is known to be true only for k = 3. For k > 3, it is known that its approximation ratio is at most 2.
Michiels, Korst, Aarts, van Leeuwen and Spieksma study a variant in which each of the m sets must contain either ceiling(n/m) or floor(n/m) items (so k = ceiling(n/m)). They extend the Balanced-LDM (BLDM) from m=2 to general m. The generalized algorithm runs in time $O(n\log n)$ . They prove that its approximation ratio for the minimum largest sum is exactly 4/3 for k = 3, 19/12 for k = 4, 103/60 for k = 5, 643/360 for k = 6, and 4603/2520 for k = 7. The ratios were found by solving a mixed integer linear program. In general (for any k), the approximation ratio is at least $2-\sum _{j=0}^{k-1}{\frac {j!}{k!}}$ and at most $2-{\frac {1}{k-1}}$ . The exact MILP results for 3,4,5,6,7 correspond to the lower bound. For k>7, no exact results are known, but the difference between the lower and upper bound is less than 0.3%. When the parameter is the number of subsets (m), the approximation ratio is exactly $2-{\frac {1}{m}}$ .
Zhang, Mouratidis and Pang show that BLDM might yield partitions with a high work-difference (difference between highest and lowest sum), both when the inputs are distributed uniformly, and when their distribution is skewed. They propose two alternative heuristics: LRM reduces the work-difference to 1/3 the work-difference of BLDM when the distribution is uniform; Meld reduces the work-difference when the distribution is skewed. A hybrid algorithm combines BLDM, LRM and Meld and adapts dynamically to different data distributions.
When k is fixed, a PTAS of Hochbaum and Shmoys can be used for balanced partitioning. When k is part of the input, no PTAS is currently known.
Dell'Amico and Martello study the problem of minimizing the largest sum when the number of items in all sets is at most k. They show that the linear-program relaxation of this variant has the same optimal value as the LP relaxation of the unconstrained variant. The expression $\max((\sum x_{i})/m,x_{1})$ , where x_i are the inputs ordered from large to small, is a lower bound for the optimal largest-sum, and its worst-case ratio is 1/2 in both variants. The improved expression $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ has worst-case ratio 2/3 in the unconstrained variant and 1/2 in the constrained variant. The approximation ratio of the modified list scheduling is 1/2 for the unconstrained variant, but it is 0 for the constrained variant (it can be arbitrarily bad). The approximation ratio of the modified LPT algorithm is at most 2. They also show that the lower bound of has a tight worst-case performance ratio of 3/4, and that their PD algorithm has a tight performance ratio of 4/3 (when m is sufficiently large).
He, Tan, Zhu and Yao consider the problem of maximizing the smallest sum. They show that the FOLDING algorithm has tight approximation ratio $\max \left({\frac {2}{k}},{\frac {1}{m}}\right)$ . They present a new algorithm, HARMONIC1, with worst-case ratio at least $\max \left({\frac {1}{k}},{\frac {1}{\lceil \sum _{i=1}^{m}{\frac {1}{i}}\rceil +1}}\right)$ . Both these algorithms are ordinal – they partition the items based only on the order between them rather than their exact values. They prove that any ordinal algorithm has ratio at most $O(1/\ln {m})$ for maximizing the smallest sum. This indicates that HARMONIC1 is asymptotically optimal. For any fixed k, any ordinal algorithm has ratio at most the smallest root of the equation $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ . When k tends to infinity, this upper bound approaches 0.

Relations between balanced and unconstrained problems

There are some general relations between approximations to the balanced partition problem and the standard (unconstrained) partition problem.

Babel, Kellerer and Kotov prove that the ratio between the unconstrained optimum and the constrained optimum is at most $2-{\frac {2}{m}}$ , and it is tight.
Kellerer and Kotov prove that every heuristic for balanced partitioning with capacity k and approximation-ratio r (for the minimum largest sum) can be employed to obtain a heuristic for unconstrained partitioning with approximation-ratio $\max \left(r,{\frac {k+2}{k+1}}-{\frac {1}{m(k+1)}}\right)$ . In particular, their $7/6$ -approximation algorithm for triplet partitioning (k = 3) can be used to obtain a heuristic for unconstrained partitioning with approximation-ratio $\max \left({\frac {7}{6}},{\frac {5}{4}}-{\frac {1}{4m}}\right)$ .

Different cardinality constraints

The cardinality constraints can be generalized by allowing a different constraint on each subset. This variant is introduced in the "open problems" section of, who call the k_i-partitioning problem. He, Tan, Zhu and Yao present an algorithm called HARMONIC2 for maximizing the smallest sum with different cardinality constraints. They prove that its worst-case ratio is at least $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ .

Categorized cardinality constraints

Another generalization of cardinality constraints is as follows. The input items are partitioned into k categories. For each category h, there is a capacity constraint k_h. Each of the m subsets may contain at most k_h items from category h. In other words: all m subsets should be independent set of a particular partition matroid. Two special cases of this problem have been studied.

Kernel partitioning

In the kernel balanced-partitioning problem, some m pre-specified items are kernels, and each of the m subsets must contain a single kernel (and an unlimited number of non-kernels). Here, there are two categories: the kernel category with capacity 1, and the non-kernel category with unlimited capacity.

Chen, He and Yao prove that the problem is NP-hard even for k = 3 (for k = 2 it can be solved efficiently by finding a maximum weight matching). They then present an algorithm called Kernel-LPT (KLPT): it assigns a kernel to each subset, and then runs the modified LPT algorithm (puts each item into the subset with the smallest sum among those that have fewer than k items). They prove that, with k = 3, KLPT has an approximation ratio ${\frac {4m-1}{3m}}$ for the minimum largest sum.^: 3 However, Chen, He and Lin^: 2 claim that its tight approximation ratio is ${\frac {3m-1}{2m}}$ for the minimum largest sum,^{[clarification needed]} and ${\frac {2m-1}{3m-2}}$ for the maximum smallest sum.

One-per-category partitioning

In another variant of this problem, there are some k categories of size m, and each subset should contain exactly one item from each category. That is, k_h = 1 for each category h.

Wu and Yao presented the layered LPT algorithm – a variant of the LPT algorithm. They prove that its approximation ratio is $2-{\frac {1}{m}}$ for minimizing the largest sum; ${\frac {1}{m}}$ for maximizing the smallest sum in the general case; and in some special cases, can be improved to ${\frac {m}{2m-1}}$ for general k and ${\frac {m-1}{2m-3}}$ for k = 3.
Li and Li presented different algorithms for the same problem. For minimizing the largest sum, they present an EPTAS for constant k, and FPTAS for constant m. For maximizing the smallest sum, they present a 1/(k − 1) approximation algorithm for the general case, and an EPTAS for constant k. They also study a more general objective: minimizing the lp-norm of the vector of sums. They prove that the layered-LPT algorithm is a 2-approximation algorithm for all norms.
Dell'Olmo, Hansen, Pallottino and Storchi study 32 different objectives for this problem. For each of the four operators max, min, sum, diff, one operator can be applied to the k items inside each subset, and then one operator can be applied to the m results for the different subsets. Each of these 16 objectives can be either maximized or minimized, for a total of 32. They show that 21 of these problems can be solved in linear time; 7 require more complex, but still polynomial-time, algorithms; 3 are NP-hard: maximizing (min, sum), minimizing (max, sum) and minimizing (diff, sum). They left open the status of minimizing (diff, diff).

References

1 2 Zhang, Jilian; Mouratidis, Kyriakos; Pang, HweeHwa (2011-06-28). "Heuristic Algorithms for Balanced Multi-Way Number Partitioning". Twenty-Second International Joint Conference on Artificial Intelligence.
1 2 3 Tsai, Li-Hui (1992-02-01). "Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling". SIAM Journal on Computing. 21 (1): 59–64. doi:10.1137/0221007. ISSN 0097-5397.
1 2 3 Dell'Amico, Mauro; Martello, Silvano (2001). "Bounds for the cardinality constrained P∥Cmax problem". Journal of Scheduling. 4 (3): 123–138. doi:10.1002/jos.68. hdl:11380/15976. ISSN 1099-1425.
↑ Garey, Michael; Johnson, David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5.
↑ Coffman, E. G.; Frederickson, G. N.; Lueker, G. S. (1984-05-01). "A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors". Mathematics of Operations Research. 9 (2): 260–266. doi:10.1287/moor.9.2.260. ISSN 0364-765X.
↑ Lueker, George S (1987-12-01). "A note on the average-case behavior of a simple differencing method for partitioning". Operations Research Letters. 6 (6): 285–287. doi:10.1016/0167-6377(87)90044-7. ISSN 0167-6377.
↑ Yakir, Benjamin (1996-02-01). "The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp". Mathematics of Operations Research. 21 (1): 85–99. doi:10.1287/moor.21.1.85. ISSN 0364-765X.
↑ Mertens, Stephan (1999-03-11). "A complete anytime algorithm for balanced number partitioning". arXiv:cs/9903011.
1 2 Kellerer, Hans; Woeginger, Gerhard (1993-09-07). "A tight bound for 3-partitioning". Discrete Applied Mathematics. 45 (3): 249–259. doi:10.1016/0166-218X(93)90013-E. ISSN 0166-218X.
1 2 Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). "3-Partitioning Problems for Maximizing the Minimum Load". Journal of Combinatorial Optimization. 6 (1): 67–80. doi:10.1023/A:1013370208101. ISSN 1573-2886. S2CID 9053629.
1 2 Kellerer, Hans; Kotov, Vladimir (1999-02-01). "A 7/6–Approximation Algorithm For 3-Partitioning And Its Application To Multiprocessor Scheduling". INFOR: Information Systems and Operational Research. 37 (1): 48–56. doi:10.1080/03155986.1999.11732368. ISSN 0315-5986.
1 2 3 4 5 6 Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "The k-partitioning problem". Mathematical Methods of Operations Research. 47 (1): 59–82. doi:10.1007/BF01193837. ISSN 1432-5217. S2CID 5594197.
↑ Michiels, Wil; Korst, Jan; Aarts, Emile; van Leeuwen, Jan (2003), Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem, Lecture Notes in Computer Science, vol. 2607, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 583–595, doi:10.1007/3-540-36494-3_51, ISBN 978-3-540-00623-7, retrieved 2021-10-15
1 2 3 Michiels, W.; Aarts, E.; Korst, J.; van Leeuwen, J.; Spieksma, F. C. R. (2012-02-01). "Computer-assisted proof of performance ratios for the Differencing Method". Discrete Optimization. 9 (1): 1–16. doi:10.1016/j.disopt.2011.10.001. ISSN 1572-5286.
↑ Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Using dual approximation algorithms for scheduling problems theoretical and practical results". Journal of the ACM. 34 (1): 144–162. doi:10.1145/7531.7535. ISSN 0004-5411. S2CID 9739129.
1 2 He, Yong; Tan, Zhiyi; Zhu, Jing; Yao, Enyu (2003-11-01). "κ-Partitioning problems for maximizing the minimum load". Computers & Mathematics with Applications. 46 (10): 1671–1681. doi:10.1016/S0898-1221(03)90201-X. ISSN 0898-1221.
1 2 Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Three-partitioning containing kernels: Complexity and heuristic". Computing. 57 (3): 255–271. doi:10.1007/bf02247409. ISSN 0010-485X. S2CID 21935917.
↑ Wu, Biao; Yao, Enyue (2007-04-20). "m-Partitioning problems with partition matroid constraint". Theoretical Computer Science. 374 (1): 41–48. doi:10.1016/j.tcs.2006.11.016. ISSN 0304-3975.
↑ Wu, Biao; Yao, En-yu (2008-03-01). "Lower bounds and modified LPT algorithm for m-partitioning problems with partition matroid constraint". Applied Mathematics-A Journal of Chinese Universities. 23 (1): 1–8. doi:10.1007/s11766-008-0101-8. ISSN 1993-0445. S2CID 16565038.
↑ Li, Weidong; Li, Jianping (2013-04-06). "Approximation algorithms for $$m$$-partitioning problems with partition matroid constraint". Optimization Letters. 8 (3): 1093–1099. doi:10.1007/s11590-013-0637-2. ISSN 1862-4472. S2CID 3385030.
↑ Dell’Olmo, Paolo; Hansen, Pierre; Pallottino, Stefano; Storchi, Giovanni (2005-09-01). "On uniform k-partition problems". Discrete Applied Mathematics. 150 (1): 121–139. doi:10.1016/j.dam.2005.02.013. ISSN 0166-218X.

[:8-1] 1 2 Zhang, Jilian; Mouratidis, Kyriakos; Pang, HweeHwa (2011-06-28). "Heuristic Algorithms for Balanced Multi-Way Number Partitioning". Twenty-Second International Joint Conference on Artificial Intelligence.

[:52-2] 1 2 3 Tsai, Li-Hui (1992-02-01). "Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling". SIAM Journal on Computing. 21 (1): 59–64. doi:10.1137/0221007. ISSN 0097-5397.

[:9-3] 1 2 3 Dell'Amico, Mauro; Martello, Silvano (2001). "Bounds for the cardinality constrained P∥Cmax problem". Journal of Scheduling. 4 (3): 123–138. doi:10.1002/jos.68. hdl:11380/15976. ISSN 1099-1425.

[Garey_&_Johnson-4] Garey, Michael; Johnson, David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5.

[5] Coffman, E. G.; Frederickson, G. N.; Lueker, G. S. (1984-05-01). "A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors". Mathematics of Operations Research. 9 (2): 260–266. doi:10.1287/moor.9.2.260. ISSN 0364-765X.

[6] Lueker, George S (1987-12-01). "A note on the average-case behavior of a simple differencing method for partitioning". Operations Research Letters. 6 (6): 285–287. doi:10.1016/0167-6377(87)90044-7. ISSN 0167-6377.

[:1-7] Yakir, Benjamin (1996-02-01). "The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp". Mathematics of Operations Research. 21 (1): 85–99. doi:10.1287/moor.21.1.85. ISSN 0364-765X.

[8] Mertens, Stephan (1999-03-11). "A complete anytime algorithm for balanced number partitioning". arXiv:cs/9903011.

[:0-9] 1 2 Kellerer, Hans; Woeginger, Gerhard (1993-09-07). "A tight bound for 3-partitioning". Discrete Applied Mathematics. 45 (3): 249–259. doi:10.1016/0166-218X(93)90013-E. ISSN 0166-218X.

[:2-10] 1 2 Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). "3-Partitioning Problems for Maximizing the Minimum Load". Journal of Combinatorial Optimization. 6 (1): 67–80. doi:10.1023/A:1013370208101. ISSN 1573-2886. S2CID 9053629.

[:6-11] 1 2 Kellerer, Hans; Kotov, Vladimir (1999-02-01). "A 7/6–Approximation Algorithm For 3-Partitioning And Its Application To Multiprocessor Scheduling". INFOR: Information Systems and Operational Research. 37 (1): 48–56. doi:10.1080/03155986.1999.11732368. ISSN 0315-5986.

[:4-12] 1 2 3 4 5 6 Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "The k-partitioning problem". Mathematical Methods of Operations Research. 47 (1): 59–82. doi:10.1007/BF01193837. ISSN 1432-5217. S2CID 5594197.

[13] Michiels, Wil; Korst, Jan; Aarts, Emile; van Leeuwen, Jan (2003), Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem, Lecture Notes in Computer Science, vol. 2607, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 583–595, doi:10.1007/3-540-36494-3_51, ISBN 978-3-540-00623-7, retrieved 2021-10-15

[:7-14] 1 2 3 Michiels, W.; Aarts, E.; Korst, J.; van Leeuwen, J.; Spieksma, F. C. R. (2012-02-01). "Computer-assisted proof of performance ratios for the Differencing Method". Discrete Optimization. 9 (1): 1–16. doi:10.1016/j.disopt.2011.10.001. ISSN 1572-5286.

[:02-15] Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Using dual approximation algorithms for scheduling problems theoretical and practical results". Journal of the ACM. 34 (1): 144–162. doi:10.1145/7531.7535. ISSN 0004-5411. S2CID 9739129.

[:10-16] 1 2 He, Yong; Tan, Zhiyi; Zhu, Jing; Yao, Enyu (2003-11-01). "κ-Partitioning problems for maximizing the minimum load". Computers & Mathematics with Applications. 46 (10): 1671–1681. doi:10.1016/S0898-1221(03)90201-X. ISSN 0898-1221.

[:3-17] 1 2 Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Three-partitioning containing kernels: Complexity and heuristic". Computing. 57 (3): 255–271. doi:10.1007/bf02247409. ISSN 0010-485X. S2CID 21935917.

[18] Wu, Biao; Yao, Enyue (2007-04-20). "m-Partitioning problems with partition matroid constraint". Theoretical Computer Science. 374 (1): 41–48. doi:10.1016/j.tcs.2006.11.016. ISSN 0304-3975.

[19] Wu, Biao; Yao, En-yu (2008-03-01). "Lower bounds and modified LPT algorithm for m-partitioning problems with partition matroid constraint". Applied Mathematics-A Journal of Chinese Universities. 23 (1): 1–8. doi:10.1007/s11766-008-0101-8. ISSN 1993-0445. S2CID 16565038.

[20] Li, Weidong; Li, Jianping (2013-04-06). "Approximation algorithms for $$m$$-partitioning problems with partition matroid constraint". Optimization Letters. 8 (3): 1093–1099. doi:10.1007/s11590-013-0637-2. ISSN 1862-4472. S2CID 3385030.

[21] Dell’Olmo, Paolo; Hansen, Pierre; Pallottino, Stefano; Storchi, Giovanni (2005-09-01). "On uniform k-partition problems". Discrete Applied Mathematics. 150 (1): 121–139. doi:10.1016/j.dam.2005.02.013. ISSN 0166-218X.