Automatic generation of FPTASes for stochastic monotone dynamic programs made easier

In this paper we go one step further in the automatic generation of FPTASes for multi-stage stochastic dynamic programs with scalar state and action spaces, in where the cost-to-go functions have a monotone structure in the state variable. While there exist a few frameworks for automatic generation of FPTASes, so far none of them is … Read more

A faster FPTAS for counting two-rowed contingency tables

In this paper we provide a deterministic fully polynomial time approximation scheme (FPTAS) for counting two-rowed contingency tables that is faster than any either deterministic or randomized approximation scheme for this problem known to date. Our FPTAS is derived via a somewhat sophisticated usage of the method of K-approximation sets and functions introduced by Halman … Read more