Multiway number partitioning

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, multiway number partitioning is the problem of partitioning a <a href="/facts/Multiset/bPFJGMDo">multiset</a> 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 <a href="/facts/Ronald_Graham/ukKzczTL">Ronald Graham</a> in 1969 in the context of the <a href="/facts/Identical-machines_scheduling/lwNSXMs6">identical-machines scheduling</a> problem.: sec.5  The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers (usually integers), whose sum is k*T.
The associated <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> 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 <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a>: 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:

<ul><li>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.</li>
<li>Minimize the largest sum. This objective is equivalent to one objective for <a href="/facts/Identical-machines_scheduling/lwNSXMs6">Identical-machines scheduling</a>. 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 <a href="/facts/Makespan/w1HEjJaQ">makespan</a> (the finish time of the last job) is minimized.</li>
<li>Maximize the smallest sum. This objective corresponds to the application of <a href="/facts/Fair_item_allocation/Hvx2XrG9">fair item allocation</a>, particularly the <a href="/facts/Maximin_share/pdUnoMuY">maximin share</a>. It also appears in voting manipulation problems, and in sequencing of maintenance actions for modular gas turbine aircraft engines. 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.</li></ul>
These three objective functions are equivalent when k=2, but they are all different when k≥3.
All these problems are <a href="/facts/NP-hardness/mQeNPv4R">NP-hard</a>, but there are various algorithms that solve it efficiently in many cases.
Some closely-related problems are:

<ul><li>The <a href="/facts/Partition_problem/LcSBAcmu">partition problem</a> - a special case of multiway number partitioning in which the number of subsets is 2.</li>
<li>The <a href="/facts/3-partition_problem/X4uW5f57">3-partition problem</a> - 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).</li>
<li>The <a href="/facts/Bin_packing_problem/T67Qe934">bin packing problem</a> - 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.</li>
<li>The <a href="/facts/Uniform_machine_scheduling/LFDtRUfD">uniform-machines scheduling</a> problem - a more general problem in which different processors may have different speeds.</li></ul>

Multiway number partitioning open-in-new

Multiway number partitioning