Tag Archives: Approximation

Constructing datatype-generic fully polynomial-time approximation schemes using generalised thinning

Shin-Cheng Mu, Yu-Han Lyu, and Akimasa Morihata. In the 6th ACM SIGPLAN workshop on Generic programming (WGP 2010), pages 97-108, Sep. 2010. [PDF]

The fully polynomial-time approximation scheme (FPTAS) is a class of approximation algorithms that is able to deliver an approximate solution within any chosen ratio in polynomial time. By generalising Bird and de Moor’s Thinning Theorem to a property between three orderings, we come up with a datatype-generic strategy for constructing fold-based FPTASs. Greedy, thinning, and approximation algorithms can thus be seen as a series of generalisations. Components needed in constructing an FPTAS are often natural extensions of those in the thinning algorithm. Design of complex FPTASs is thus made easier, and some of the resulting algorithms turn out to be simpler than those in previous works.

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.