1
$\begingroup$

In the partition problem we want to partition a set $S$ of positive integers into two sets $S_{1}$ and $S_{2}$ such that the sum of the integers in the two sets is the same.

The optimization version of the problem is NP-Hard, in the following wikipedia page an 7/6 approximation algorithm is described. In that algorithm, we sort the original set $S$, traverse the new sorted set in descending order and send each element to the set $S_{i}, i\in\{1,2\}$ that has the minimum total sum at the given moment.

My question is, does the traversal have to be in descending order? If we do it in ascending, does anything change in the final approximation ratio?

|cite|improve this question
$\endgroup$
1
$\begingroup$

Consider what happens if you have 1000 items of size 1, and 1 of size 1000. Optimally, you would have 2 sets of size 1000, but if you followed the heuristic with items in ascending order, you will have one set of 500, and one of 1500, for a 3/2 approximation, worse than 7/6.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I suppose a simpler example would have been 2 items of size 1, and one of size 2. It would still be a 3/2 approximation, but somehow "feels" closer to optimal, as it is only off by 1 (item or unit). $\endgroup$ – Algorithms with Attitude Jan 25 '17 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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