Optimization Online


A faster FPTAS for counting two-rowed contingency tables

Tzvi Alon(alontzvi***at***gmail.com)
Nir Halman(halman***at***huji.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society