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.

Leave a Comment

Your email address will not be published. Required fields are marked *