A faster FPTAS for counting two-rowed contingency tables

DOI10.1016/j.dam.2020.05.036OpenAlexW3037816930MaRDI QIDQ1983128

Tzvi Alon, Nir Halman

Publication date: 15 September 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.05.036

zbMATH Keywords

dynamic programmingcontingency tables\(K\)-approximation sets and functions

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Lower bounds for contingency tables via Lorentzian polynomials

Cites Work

• Unnamed Item
• A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• Polynomial-time counting and sampling of two-rowed contingency tables
• On the complexity of energy storage problems
• Approximating convex functions via non-convex oracles under the relative noise model
• On the number of Eulerian orientations of a graph
• Pseudorandom Generators for Polynomial Threshold Functions
• A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
• Approximating the Nonlinear Newsvendor and Single-Item Stochastic Lot-Sizing Problems When Data Is Given by an Oracle
• Faster FPTASes for Counting and Random Generation of Knapsack Solutions
• Counting independent sets up to the tree threshold
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand
• Approximating the Permanent
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• Approximate counting by dynamic programming
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
• An FPTAS for #Knapsack and Related Counting Problems
• A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs
• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant

This page was built for publication: A faster FPTAS for counting two-rowed contingency tables