A faster FPTAS for counting two-rowed contingency tables

  • Tzvi Alon
  • Nir Halman
    • Categories Approximation Algorithms, Dynamic Programming Tags , , , Short URL: https://optimization-online.org/?p=15575

    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 et al. [Math. Oper. Res. 34, (2009), pp. 674--685].

    Citation

    Hebrew University of Jerusalem

    Article

    Download

    View A faster FPTAS for counting two-rowed contingency tables