2
$\begingroup$

Do we know anything about the hardness of the optimization version of the multiway number partitioning problem when the set of numbers to partition consists of the reciprocals of the first $n$ integers? That is, for $n, k\in \mathbb{N}$, find sets $S_1,\dots,S_k$ such that

  • $\bigcup_{i=1}^k S_i = \{1, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n}\}$,
  • $S_i \cap S_j = \emptyset$ for $i\neq j$

that minimizes the largest difference between two sets, i.e., that minimizes $\max_{i,j}| \sum_{x \in S_i} x - \sum_{y \in S_j} y|$.

I am curious about other objective functions too. I am mainly interested about the effect of restricting the set of numbers to partition.

$\endgroup$
2
  • $\begingroup$ Could you please clarify, if $S_i$ is a set or a multi-set? $\endgroup$ Mar 7 at 7:58
  • 1
    $\begingroup$ $S_i \ \subseteq \{1, \frac{1}{2}, \ldots, \frac{1}{n}\}$ is a simple set. $\endgroup$ Mar 7 at 14:08

1 Answer 1

0
$\begingroup$

The sum of all elements is H_n (n-th harmonic number), approximately ln n + c where ln is the natural logarithm and c is quite small.

If k > H_n then the average size of a set is less than 1. So take {1} as the first set and you have H_n - 1 and k-1 sets left. If the average is > 1/2 then you take the set {1/2} etc until you have enough left for the sets. At that point it’s quite similar to bin packing, except the problem isn’t “how many bins of size s are needed” but “what is the smallest s so that k bins all contain more than s”.

Now if you were given n numbers then the problem size would be O(n) and the problem would be NP-complete. But the problem is given by two numbers, so the problem size is just log n + log k, so it’s much much harder relative to the problem size.

$\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.