Tzvi Alon

Automatic generation of FPTASes for stochastic monotone dynamic programs made easier

  • Tzvi Alon
  • Nir Halman
    • Categories Approximation Algorithms, Dynamic Programming Tags , ,

    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

  • Tzvi Alon
  • Nir Halman
    • Categories Approximation Algorithms, Dynamic Programming Tags , , ,

    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