2016/11/03 by Tzvi Alon, Alon, Tzvi
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1611.00992
openalex publication_date 2016/11/03 · openalex created_date 2016/11/11 · openalex updated_date 2026/07/28
In this thesis we develop FPTASs for the counting problems of m-tuples, contingency tables with two rows, and 0/1 knapsack. For the problem of counting m-tuples, we design two algorithms, one is strongly polynomial. As far as we know, these are the first FPTASs for this problem. For the problem of counting contingency tables we improve significantly over the running time of existing algorithms. For the problem of counting 0/1 knapsack solutions, we design a simple strongly polynomial algorithm, with similar running times to the existing algorithms. Our results are derived by using, as well as expanding, the method of K-approximation sets and functions.