- | ||||
|
![]()
|
A faster FPTAS for counting two-rowed contingency tables
Tzvi Alon(alontzvi 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |