0
$\begingroup$

I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. But I am not really interested in THE optimal solution. I am interested in a FAST algorithm that generates some good partition wrt the criterion.

Let us say a set is [1,23,12,2456,234,16,188,22] and needs to be divided 3-ways. When partitioning we try to minimize the max difference between the size of all subsets.

One quick partition that can be generated is {[1,23,12],[2456,234,16],[188,22]}. This may not be optimal or maybe it is. It does not matter in this context.

We could have an algorithm: put 1st element in 1st set, 2nd element in 2nd set, all others in 3rd set. This would give us: {[1],[23],[2456,234,16,188,22]}. One can see this algo will be very fast but wrt to our criterion, it does not necessarily give a good-looking solution.

Can someone suggest existing work in this direction?

$\endgroup$
3
  • 1
    $\begingroup$ I don't think it's clear what you are asking. Dividing the set into 3 even sets (+/- 1 element) is trivial, and appears to be optimal. What prevents that from being used? $\endgroup$
    – Cort Ammon
    Apr 2, 2018 at 23:57
  • 1
    $\begingroup$ I hope you're aware that finding exactly balanced partitions is basically the Subset Sum problem, which is NP-complete. That should immediately give you caution. $\endgroup$ Apr 3, 2018 at 0:01
  • $\begingroup$ I am assuming that criteria may widely vary. is there some general analysis? $\endgroup$
    – user_1_1_1
    Apr 3, 2018 at 0:01

1 Answer 1

4
$\begingroup$

The following is directly taken from pages 358-360 of The Nature of Computation by Moore and Mertens and I think addresses your problem directly.

Imagine that you run a computer center with $p$ identical machines, or a parallel computer with $p$ processors, for some constant $p$. You are given $n$ jobs with running times $t_1,t_2,...,t_n$. Your task is to find a schedule - a function $f:\{1,...,n\}\rightarrow\{1,...,p\}$ that assigns the $j$th job to the $f(j)$th machine.
The load on the $j$th machine is the total time it takes to run the jobs assigned to it, $$ L_j = \sum_{i:f(i)=j} t_i\,. $$ Since the machines run in parallel, the time it takes us to finish all the jobs is the maximum load on any machine, $$ M=\max_{i\leq j\leq p} L_j\,. $$ We call this time the makespan, and your goal is to minimize it. This gives the following problem:

Makespan
Input: A set of $n$ running times $t_i\geq0,\,i=1,...,n$
Output: A function $f: \{1,...,n\}\rightarrow\{1,...,p\}$ that minimizes the makespan $$M = \max_{1 \leq j \leq p} \sum_{i:f(i)=j}t_i$$

Exercise 9.3 Reduce Integer Partitioning to the case of Makespan where $p=2$.

There is, however, a simple algorithm that comes with a quality guarantee. The idea is to divide tasks into two groups, "large" and "small", and schedule the large tasks first. Let $T_{\text{tot}}=\sum_{j=1}^n t_j$ be the total running time of all the tasks. We choose some constant $\eta > 0$, say $\eta = 1/10$. We call the $j$th task large if its running time is at least a fraction $\eta$ of the total, $t_j \geq \eta\,T_{\text{tot}}$, and small if $t_j < \eta\,T_{\text{tot}}$.
The algorithm then proceeds in two phases:

  1. Find a schedule that minimizes the makespan of the large tasks, using exhaustive search.
  2. Distribute the small tasks by giving each one to the machine with the smallest load so far, regardless of that tasks's running time.

How long does this algorithm take? Since there are at most $1/\eta$ large tasks, there are $p^{1/\eta}$ ways to schedule them. Since $p$ and $\eta$ are constants, this gives a constant number of possible schedules to explore in phase 1, and we can check all of them in polynomial time using exhaustive search. Phase 2 clearly runs in polynomial time as well.
Now let $M$ denote the makespan of the schedule produced by this algorithm. How does it compare to $M_{\text{opt}}$? Let $M_{\text{large}}$ denote the maximum load of a machine after phase 1, i.e., the minimum makespan of the large tasks. Since adding the small tasks can only increase the makespan, we have $M_{\text{large}} \leq M_{\text{opt}}$. If the algorithm manages to fit all the small tasks in phase 2 without increasing the makespan, putting them on machines with load less than $M_{\text{large}}$, then $M = M_{\text{large}}$. But since $M_{\text{opt}} \leq M$, in this case $M = M_{\text{opt}}$ and the algorithm performs perfectly.
So, we will focus on the harder case where the makespan increases in phase 2, so that $M > M_{\text{large}}$ and our schedule for the small tasks might not be optimal. Let $L_j$ denote the load of machine $j$ after phase 2. Without loss of generality, we can assume that $L_1 \geq L_2 \geq ... \geq L_p$. Since $L_1 = M > M_{\text{large}}$, we know that at least one small task was added to machine 1.
Let $t$ be the running time of the last such task. Since our strategy greedily assigns small tasks to the machines with the smallest load, the load of machine 1 must have been less than or equal to the others just before this task was added. This means that, for all $2 \leq j \leq p$, $$ M-t \leq L_j \leq M\,. $$ Since $t<\eta\,T_{\text{tot}}$, we also have $$ T_{\text{tot}} = M + \sum_{j=2}^p L_j \geq pM-(p-1)t\geq pM-\eta(p-1)T_{\text{tot}}\,. $$ Rearranging this gives an upper bound on M, $$ M \leq \frac{T_{\text{tot}}}{p}(1+\eta(p-1))\,. $$ On the other hand, the best schedule we could hope for would be perfectly balanced, keeping all the machines busy all the time. Thus the optimum makespan is bounded below by $$ M_{\text{opt}}\geq\frac{T_{\text{tot}}}{p}\,. $$ Combining this lower bound on $M_{\text{opt}}$ with the upper bound we have on $M$ gives an approximation ratio $$ \rho \leq \frac{M}{M_{\text{opt}}} \leq 1+\eta(p-1)\,. $$ By setting $\eta = \epsilon/(p-1)$, we can approximate $M_{\text{opt}}$ within a factor of $\rho = 1+\epsilon$ for arbitrarily small $\epsilon > 0$. In fact, we can define an algorithm that takes both the problem instance and $\epsilon$ as inputs, and returns a $(1+\epsilon)$-approximation. For each fixed $\epsilon$, this algorithm runs in polynomial time. Such an algorithm is called a polynomial-time approximation scheme or PTAS.
On the face of it, a PTAS seems to be sufficient for all practical purposes. It allows us to find solutions within 1%, 0.1%, 0.01% ... of the optimum, each in polynomial time. However, improving the quality of the approximation comes at a cost, since the running time increases as $\epsilon$ decreases. Our PTAS for Makespan, for example, has to explore $p^{1/\eta} = p^{(p-1)/\epsilon}$ possible schedules in phase 1, so its running time grows exponentially as a function of $1/\epsilon$. Even for $p=2$ and $\epsilon = 0.01$, this number is $2^{100}$ - hardly a constant that we can ignore.
We would prefer an algorithm whose running time is polynomial both in $n$ and in $1/\epsilon$. Such an algorithm is called a fully polynomial-time approximation scheme, or FPTAS for short. There is, in fact, an FPTAS for Makespan, which we will not describe here.

The end of chapter notes further recommend the "outstanding" book Approximation Algorithms by Vazirani, from which this algorithm is apparently taken.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.