Gerhard J. Woeginger

We derive results of the following flavor:

If a combinatorial optimization problem can be formulated via a dynamic

program of a certain structure and if the involved cost and transition

functions satisfy certain arithmetical and structural conditions, then

the optimization problem automatically possesses a fully polynomial time

approximation scheme (FPTAS).

Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>>