Multiway number partitioning

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the identical-machines scheduling problem.[1]: sec.5  The problem is parametrized by a positive integer k, and called k-way number partitioning.[2] The input to the problem is a multiset S of numbers (usually integers), whose sum is k*T.

The associated decision problem is to decide whether S can be partitioned into k subsets such that the sum of each subset is exactly T. There is also an optimization problem: find a partition of S into k subsets, such that the k sums are "as near as possible". The exact optimization objective can be defined in several ways:

  • Minimize the difference between the largest sum and the smallest sum. This objective is common in papers about multiway number partitioning, as well as papers originating from physics applications.[2]
  • Minimize the largest sum. This objective is equivalent to one objective for Identical-machines scheduling. There are k identical processors, and each number in S represents the time required to complete a single-processor job. The goal is to partition the jobs among the processors such that the makespan (the finish time of the last job) is minimized.
  • Maximize the smallest sum. This objective corresponds to the application of fair item allocation, particularly the maximin share. It also appears in voting manipulation problems,[3] and in sequencing of maintenance actions for modular gas turbine aircraft engines.[4][5] Suppose there are some k engines, which must be kept working for as long as possible. An engine needs a certain critical part in order to operate. There is a set S of parts, each of which has a different lifetime. The goal is to assign the parts to the engines, such that the shortest engine lifetime is as large as possible.

These three objective functions are equivalent when k=2, but they are all different when k≥3.[6][7]

All these problems are NP-hard,[8] but there are various algorithms that solve it efficiently in many cases.

Some closely-related problems are:

  • The partition problem - a special case of multiway number partitioning in which the number of subsets is 2.
  • The 3-partition problem - a different and harder problem, in which the number of subsets is not considered a fixed parameter, but is determined by the input (the number of sets is the number of integers divided by 3).
  • The bin packing problem - a dual problem in which the total sum in each subset is bounded, but k is flexible; the goal is to find a partition with the smallest possible k. The optimization objectives are closely related: the optimal number of d-sized bins is at most k, iff the optimal size of a largest subset in a k-partition is at most d.[9]
  • The uniform-machines scheduling problem - a more general problem in which different processors may have different speeds.
  1. ^ Graham, Ron L. (1969-03-01). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. doi:10.1137/0117039. ISSN 0036-1399.
  2. ^ a b Mertens, Stephan (2006), "The Easiest Hard Problem: Number Partitioning", in Allon Percus; Gabriel Istrate; Cristopher Moore (eds.), Computational complexity and statistical physics, Oxford University Press US, p. 125, arXiv:cond-mat/0310317, Bibcode:2003cond.mat.10317M, ISBN 978-0-19-517737-4
  3. ^ Walsh, Toby (2009-07-11). "Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule" (PDF). Written at Pasadena, California, USA. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. San Francisco, California, USA: Morgan Kaufmann Publishers Inc. pp. 324–329. Archived (PDF) from the original on 2020-07-10. Retrieved 2021-10-05.
  4. ^ Friesen, D. K.; Deuermeyer, B. L. (1981-02-01). "Analysis of Greedy Solutions for a Replacement Part Sequencing Problem". Mathematics of Operations Research. 6 (1): 74–87. doi:10.1287/moor.6.1.74. ISSN 0364-765X.
  5. ^ Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (1982-06-01). "Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System". SIAM Journal on Algebraic and Discrete Methods. 3 (2): 190–196. doi:10.1137/0603019. ISSN 0196-5212.
  6. ^ Korf, Richard Earl (2010-08-25). "Objective Functions for Multi-Way Number Partitioning". Third Annual Symposium on Combinatorial Search. 1: 71–72. doi:10.1609/socs.v1i1.18172. S2CID 45875088.
  7. ^ Walter, Rico (2013-01-01). "Comparing the minimum completion times of two longest-first scheduling-heuristics". Central European Journal of Operations Research. 21 (1): 125–139. doi:10.1007/s10100-011-0217-4. ISSN 1613-9178. S2CID 17222989.
  8. ^ Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. p. 238. ISBN 978-0716710448.
  9. ^ Cite error: The named reference :02 was invoked but never defined (see the help page).