Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with FPTAS:
TR01-084 | 1st October 2001
Gerhard J. Woeginger

When does a dynamic programming formulation guarantee the existence of an FPTAS?

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).

... more >>>

TR14-065 | 2nd May 2014
Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

Approximate Counting of Matchings in $(3,3)$-Hypergraphs

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 >>>

ISSN 1433-8092 | Imprint