0
$\begingroup$

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?

Cheers

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ What is the "number partition problem"? $k$-partition? $\endgroup$
    – Juho
    Commented Apr 2, 2013 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
    Commented Apr 3, 2013 at 18:48

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\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.