# fair partitioning of set S into k partitions

There is a set S containing N integers each with value 1<=X<=10^6. The problem is to partition the set S into k partitions. The value of a partition is the sum of the elements present in it. Partition is to be done in such a way the total value of the set S is fairly distributed amongst the k partitions. The mathematical meaning of fair also needs to be defined (e.g. the objective could be to minimize the standard deviation of the values of the partitions from the average value of the set S (which is, sum(S)/k))

e.g. S = {10, 15, 12, 13, 30, 5}, k=3

A good partitioning would be {30}, {10, 15}, {12, 13, 5}

A bad partitioning would be {30, 5}, {10, 15}, {12, 13}

First question is to mathematically express condition for one partition to be better than the other. Second question is to how to solve the problem. The problem is NP-Hard. Are there any heuristics?

In the problem that I am trying to solve N <= (k*logX)^2 and K varies from 2 to 7.

==================================================================================

Based on other related SO questions, there are two reasonable functions to evaluate a distribution:

a) Minimize the value of the partition with the maximum value.

On a second thought, this is not a good metric. Consider, a set {100, 40, 40} to be partitioned into three subsets. This metric does not distinguish between the following two distributions even though one is clearly better than the other.

Distribution 1: {100}, {40}, {40} and Distribution 2: {100}, {40, 40}, {}

b) Minimize the maximum of the difference of any two values in a given partition i.e minimize max|A-B| for any A, B

-
for the record, `N <= (7*ln(10^6))^2 ~= 9300`; does that sound about right? –  ninjagecko Jun 23 '11 at 14:38
yes thats correct –  Akhil Jun 23 '11 at 15:19
Exact same question with a really good answer here. stackoverflow.com/questions/6454598/… –  Corey Alexander Jun 24 '11 at 6:49
My Question is pretty much the same. I found the answer, i've posted it. –  st0le Jun 24 '11 at 9:39
@Corey - Their is a gross difference between the two questions. In my problem, rearrangement is allowed, while in the referred question the number should not be rearranged –  Akhil Jun 24 '11 at 17:56

I think a good metric will be:

``````let the result set be s1,s2,...,sk
let MAX be max{sum(si) for each i}
f({s1,...,sk}) = Sigma(MAX-sum(si)) for each i)
``````

the upside: a perfect distribution will yield always 0!
the downside: if there is none perferct solution, the best result will not yield 0.

a greedy heuristic for this problem will be:

``````sorted<-sort(S) (let's say sorted[0] is the highest)
s1=s2=...=sk= {}
for each x in sorted:
s <- find_min() (*)
``````

where find_min() yields s such that sum(s) <= sum(si) for each si.

this solution's will yield f (metrics defined above) such that `f(sol) <= (k-1)*max{S}` (from here it is a proof for this bound):

claim: for each subset s, `MAX- sum(s) <= max{S}`
proof - by induction: at each step, the claim is true for the temporary solution.
in each step, let MAX be max{sum(si)} at the start of the iteration (before the add)!

``````base: the set of subsets at start is {},{},.. MAX=sum(si)=0 for each si.
step: assume the assumption is true for iteration i, we'll show it is also true for iteration i+1:
let s be the set that x was added to, then MAX-sum(s) <= max{S} (induction assumption).
if sum(s) + x <= MAX: we are done, MAX was not changed.
else: we sorted the elements at start, so x <= max{S}, and thus if s was chosen
(sum(si) >= sum(s) for each si) and sum(s) + x > MAX then: for each si, sum(si) + x >=
sum(s) + x, so sum(s)+x - sum(si) <= x <= max{S}. since sum(s)+x will be the MAX next
iteration, we are done.
``````

because for each set `MAX-sum(si) <= max{S}` (and obviously, for the max set, `MAX-sum(si)=0`), at overall `Sigma(MAX-sum(si)) <= (k-1)*max{S}`, as promised.

EDIT :
I had some spare time, so I programmed both heuristics suggested by me and by @Akhil, and both metrics, first of all, both results are conclusive (according to Wilcoxon's pair-t test), but which is better is defined by which metric you choose, surprisingly, the algorithm which tried to minimize f() (@Akhil`s) scored lower for this same f, but higher for the second metric.

-
@amit: neat solution and a very good effort. I am putting another greedy approach as an answer below. I gave it a few tries but could not prove any bound. Can you give it a try? –  Akhil Jun 27 '11 at 2:19
@amit: can you please define the 'x' and the 'y' axis in your answer, for completeness/clarity? –  Akhil Jun 27 '11 at 20:13
@Akhil: It is labled: for both histograms x axis is metric value (for each graph a different metric) while y axis is frequency –  amit Jun 28 '11 at 8:07
@amit: graph?? The metric is supposed to be continuous (being the objective value). Also, what does frequency represent(frequency of what?) –  Akhil Jun 28 '11 at 16:29
@Akhil it is a histogram, I produced 150 random samples, and ran both algorithms on each sample. then I produced the histogram with 20 bins for each metric - to try and show which is better. it is pretty standard for comparing two heuristics... –  amit Jun 28 '11 at 17:28
show 1 more comment

One heuristic would be to spread the larger weights among the bags as evenly as possible, leaving enough smaller weights that you're now left with a subproblem with a large number of degrees of freedom. Repeat into sub-subproblems if necessary. This heuristic assumes your distribution is not too geometric, e.g. `{1000} and {100, 10, 1}`, and slightly assumes that your penalty function will penalize nil-assignments or very large outliers.

For example:

``````distributeFairly(numbers, bins):
distributeFairlySubproblem(numbers, bins):
n = len(numbers)
numElementsToDefer = min(-n//3,20*k)  # modify as appropriate, e.g. to avoid len(toPlace)<len(toDefer)

toDefer = numbers[-numElementsToDefer:]
toPlace = numbers[:-numElementsToDefer]

newBins = shoveThemIn(toPlace, copy(bins))
return distributeFairlySubproblem(toDefer, newBins)

initialGuess = distributeFairlySubproblem(sorted(numbers,reverse=True), [[]]*k)
return anneal(initialGuess)
``````
-
we also need to give a good comparison function to compare two partitions –  Akhil Jun 23 '11 at 15:21
Can you please elaborate a little more on your heuristic –  Akhil Jun 24 '11 at 19:00
The text passage describes a problem of partitioning a set of integers into k partitions in a "fair" manner, where "fair" is defined as minimizing the standard deviation of the sum of the elements in each partition from the average value of the set. The passage also provides a heuristic approach to solving the problem and discusses different metrics for evaluating the quality of a partition.
multiple_questions

the passage contains multiple questions or problems:
1. how to mathematically express the condition for one partition to be better than the other.
2. how to solve the partitioning problem.
3. whether there are any heuristics for solving the problem.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# fair partitioning of set S into k partitions

There is a set S containing N integers each with value 1<=X<=10^6. The problem is to partition the set S into k partitions. The value of a partition is the sum of the elements present in it. Partition is to be done in such a way the total value of the set S is fairly distributed amongst the k partitions. The mathematical meaning of fair also needs to be defined (e.g. the objective could be to minimize the standard deviation of the values of the partitions from the average value of the set S (which is, sum(S)/k))

e.g. S = {10, 15, 12, 13, 30, 5}, k=3

A good partitioning would be {30}, {10, 15}, {12, 13, 5}

A bad partitioning would be {30, 5}, {10, 15}, {12, 13}

First question is to mathematically express condition for one partition to be better than the other. Second question is to how to solve the problem. The problem is NP-Hard. Are there any heuristics?

In the problem that I am trying to solve N <= (k*logX)^2 and K varies from 2 to 7.

==================================================================================

Based on other related SO questions, there are two reasonable functions to evaluate a distribution:

a) Minimize the value of the partition with the maximum value.

On a second thought, this is not a good metric. Consider, a set {100, 40, 40} to be partitioned into three subsets. This metric does not distinguish between the following two distributions even though one is clearly better than the other.

Distribution 1: {100}, {40}, {40} and Distribution 2: {100}, {40, 40}, {}

b) Minimize the maximum of the difference of any two values in a given partition i.e minimize max|A-B| for any A, B

-
for the record, `N <= (7*ln(10^6))^2 ~= 9300`; does that sound about right? –  ninjagecko Jun 23 '11 at 14:38
yes thats correct –  Akhil Jun 23 '11 at 15:19
Exact same question with a really good answer here. stackoverflow.com/questions/6454598/… –  Corey Alexander Jun 24 '11 at 6:49
My Question is pretty much the same. I found the answer, i've posted it. –  st0le Jun 24 '11 at 9:39
@Corey - Their is a gross difference between the two questions. In my problem, rearrangement is allowed, while in the referred question the number should not be rearranged –  Akhil Jun 24 '11 at 17:56

I think a good metric will be:

``````let the result set be s1,s2,...,sk
let MAX be max{sum(si) for each i}
f({s1,...,sk}) = Sigma(MAX-sum(si)) for each i)
``````

the upside: a perfect distribution will yield always 0!
the downside: if there is none perferct solution, the best result will not yield 0.

a greedy heuristic for this problem will be:

``````sorted<-sort(S) (let's say sorted[0] is the highest)
s1=s2=...=sk= {}
for each x in sorted:
s <- find_min() (*)
``````

where find_min() yields s such that sum(s) <= sum(si) for each si.

this solution's will yield f (metrics defined above) such that `f(sol) <= (k-1)*max{S}` (from here it is a proof for this bound):

claim: for each subset s, `MAX- sum(s) <= max{S}`
proof - by induction: at each step, the claim is true for the temporary solution.
in each step, let MAX be max{sum(si)} at the start of the iteration (before the add)!

``````base: the set of subsets at start is {},{},.. MAX=sum(si)=0 for each si.
step: assume the assumption is true for iteration i, we'll show it is also true for iteration i+1:
let s be the set that x was added to, then MAX-sum(s) <= max{S} (induction assumption).
if sum(s) + x <= MAX: we are done, MAX was not changed.
else: we sorted the elements at start, so x <= max{S}, and thus if s was chosen
(sum(si) >= sum(s) for each si) and sum(s) + x > MAX then: for each si, sum(si) + x >=
sum(s) + x, so sum(s)+x - sum(si) <= x <= max{S}. since sum(s)+x will be the MAX next
iteration, we are done.
``````

because for each set `MAX-sum(si) <= max{S}` (and obviously, for the max set, `MAX-sum(si)=0`), at overall `Sigma(MAX-sum(si)) <= (k-1)*max{S}`, as promised.

EDIT :
I had some spare time, so I programmed both heuristics suggested by me and by @Akhil, and both metrics, first of all, both results are conclusive (according to Wilcoxon's pair-t test), but which is better is defined by which metric you choose, surprisingly, the algorithm which tried to minimize f() (@Akhil`s) scored lower for this same f, but higher for the second metric.

-
@amit: neat solution and a very good effort. I am putting another greedy approach as an answer below. I gave it a few tries but could not prove any bound. Can you give it a try? –  Akhil Jun 27 '11 at 2:19
@amit: can you please define the 'x' and the 'y' axis in your answer, for completeness/clarity? –  Akhil Jun 27 '11 at 20:13
@Akhil: It is labled: for both histograms x axis is metric value (for each graph a different metric) while y axis is frequency –  amit Jun 28 '11 at 8:07
@amit: graph?? The metric is supposed to be continuous (being the objective value). Also, what does frequency represent(frequency of what?) –  Akhil Jun 28 '11 at 16:29
@Akhil it is a histogram, I produced 150 random samples, and ran both algorithms on each sample. then I produced the histogram with 20 bins for each metric - to try and show which is better. it is pretty standard for comparing two heuristics... –  amit Jun 28 '11 at 17:28
show 1 more comment

One heuristic would be to spread the larger weights among the bags as evenly as possible, leaving enough smaller weights that you're now left with a subproblem with a large number of degrees of freedom. Repeat into sub-subproblems if necessary. This heuristic assumes your distribution is not too geometric, e.g. `{1000} and {100, 10, 1}`, and slightly assumes that your penalty function will penalize nil-assignments or very large outliers.

For example:

``````distributeFairly(numbers, bins):
distributeFairlySubproblem(numbers, bins):
n = len(numbers)
numElementsToDefer = min(-n//3,20*k)  # modify as appropriate, e.g. to avoid len(toPlace)<len(toDefer)

toDefer = numbers[-numElementsToDefer:]
toPlace = numbers[:-numElementsToDefer]

newBins = shoveThemIn(toPlace, copy(bins))
return distributeFairlySubproblem(toDefer, newBins)

initialGuess = distributeFairlySubproblem(sorted(numbers,reverse=True), [[]]*k)
return anneal(initialGuess)
``````
-
we also need to give a good comparison function to compare two partitions –  Akhil Jun 23 '11 at 15:21
Can you please elaborate a little more on your heuristic –  Akhil Jun 24 '11 at 19:00
user
The text passage describes a problem of partitioning a set of integers into k partitions in a "fair" manner, where "fair" is defined as minimizing the standard deviation of the sum of the elements in each partition from the average value of the set. The passage also provides a heuristic approach to solving the problem and discusses different metrics for evaluating the quality of a partition.

TYPE: MULTIPLE_QUESTIONS

The passage contains multiple questions or problems:
1. How to mathematically express the condition for one partition to be better than the other.
2. How to solve the partitioning problem.
3. Whether there are any heuristics for solving the problem.