I've been given a task to implement two algorithms (an exact algorithm and fully polynomial approximation scheme) for number partitioning problem. I found out that I can use some modification of heuristic approach (like complete differencing tree method) or just plain brute-force for the former, but I have a lot of trouble with the latter... can anyone point some resources where FPTAS for NPP is discussed or guidelines how to construct one?


  • 4
    $\begingroup$ What is the "number partition problem"? $k$-partition? $\endgroup$ – Juho Apr 2 '13 at 20:20
  • $\begingroup$ No, it's just standard Partition problem, with two subsets having equal/nearly equal sums of their elements. "Number Partition Problem" is a term that I found in some literature (I think it's used to distinguish it from graph partitioning). $\endgroup$ – barti90 Apr 3 '13 at 18:48

http://en.wikipedia.org/wiki/Partition_problem mentions two textbooks which cover the subject:

Hans Kellerer; Ulrich Pferschy; David Pisinger (2004), Knapsack problems, Springer, p. 97, ISBN 9783540402862

Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 0-471-92420-2. MR 1086874.

| cite | improve this answer | |

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.