**Last update: August 26, 2013**

Code and supplementary proofs accompanying the paper: Constructing Datatype-Generic Fully Polynomial-Time Approximation Schemes Using Generalised Thinning, by Yu-Han Lyu, Akimasa Morihata, and me.

The supplementary proofs mainly consist of proofs regarding the individual problems in the paper.

The file fptas.zip consists of the following Haskell modules:

`KnapsackSpec`

: specification of the 0-1 knapsack problem.`Knapsack`

: a thinning algorithm solving knapsack (`knapsack`

), and an approximation algorithm (`knapsack_apx`

).`KnapsackTest`

: some QuickCheck properties to test the code.`PartTreesSpec`

: specification of the maximal tree partition problem.`PartTrees`

: a thinning algorithm solving the tree partition problem (`mtp`

), and an approximation algorithm (`mtp_apx`

).`PartTreesTest`

: some QuickCheck properties to test the code.`Utilities`

: some utilities used by`PartTreesSpec`

.`Merging`

: generalised merging and bumping functions for both programs.

The problem instances generated by QuickCheck very rapidly get too large in size. The function `smallCheck`

defined in both `*Test`

modules restricts the sizes of instances generated.