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 (
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 (
PartTreesTest: some QuickCheck properties to test the code.
Utilities: some utilities used by
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.