A faster FPTAS for counting two-rowed contingency tables

Tzvi Alon(alontzvigmail.com)
Nir Halman(halmanhuji.ac.il)

Abstract: 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].

Keywords: Approximate counting, contingency tables, dynamic programming, K-approximation sets and functions

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Other Topics (Dynamic Programming )

Citation: Hebrew University of Jerusalem

Download: [PDF]

Entry Submitted: 12/13/2018
Entry Accepted: 12/14/2018
Entry Last Modified: 12/13/2018

Modify/Update this entry