Last update: June 23, 2010
Code accompanying a forthcoming paper of Yu-Han Lyu, Akimasa Morihata, and me: Constructing Datatype-Generic Fully Polynomial-Time Approximation Schemes Using Generalised Thinning.
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.