approximate counting

A faster FPTAS for counting two-rowed contingency tables

  • Tzvi Alon
  • Nir Halman
    • Categories Approximation Algorithms, Dynamic Programming Tags , , ,

    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 … Read more

    A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy

  • Nir Halman
    • Categories Approximation Algorithms, Dynamic Programming Tags , ,

    Given $n$ elements with nonnegative integer weights $w=(w_1,\ldots,w_n)$, an integer capacity $C$ and positive integer ranges $u=(u_1,\ldots,u_n)$, we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most $C$. We give a deterministic algorithm that estimates the number of solutions to within … Read more