<p><a href="http://en.wikipedia.org/wiki/Partition_problem" rel="nofollow">http://en.wikipedia.org/wiki/Partition_problem</a> mentions two textbooks which cover the subject:</p>

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

<p>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.</p>

CC BY-SA 3.0
2013-04-03T06:26:57.193Z
2013-04-03T06:26:57.193Z
user13407
<p>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?</p>

<p>Cheers</p>

CC BY-SA 3.0
2013-04-02T20:20:24.470Z
What is the "number partition problem"? [$k$-partition](http://en.wikipedia.org/wiki/Partition_problem#The_k-partition_problem)?
Juho
CC BY-SA 3.0
2013-04-03T18:48:03.783Z
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).
barti90
<cc.complexity-theory><ds.algorithms><approximation-algorithms><partition-problem>
FPTAS for Number Partition Problem
barti90
# FPTAS for Number Partition Problem

(Asked by: username_0 on 2013-04-02)

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

**Tags:** cc.complexity-theory, ds.algorithms, approximation-algorithms, partition-problem
> **Comments:**
> **username_1**: What is the "number partition problem"? [$k$-partition](http://en.wikipedia.org/wiki/Partition_problem#The_k-partition_problem)?  
> **username_0**: 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).  

---

## 1 answers

### Answer by username_2 on 2013-04-03. Score: 1

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


---

