Fully Polynomial-Time Approximation by Thinning

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.