A faster FPTAS for counting two-rowed contingency tables
type: Item
instance of: scholarly article
title: A faster FPTAS for counting two-rowed contingency tables
author: Tzvi Alon
author: Nir Halman
published in: Discrete Applied Mathematics
publication date: 2021-09-15T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7395738
zbMATH Keywords: contingency tables
zbMATH Keywords: dynamic programming
zbMATH Keywords: \(K\)-approximation sets and functions
MaRDI profile type: Publication
full work available at URL: j.dam.2020.05.036
OpenAlex ID: W3037816930
cites work: Q3549606
cites work: A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
cites work: Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
cites work: Testing for independence in a two-way table: New interpretations of the chi-square statistic
cites work: Approximate counting by dynamic programming
cites work: Approximately Counting Hamilton Paths and Cycles in Dense Graphs
cites work: Polynomial-time counting and sampling of two-rowed contingency tables
cites work: An FPTAS for #Knapsack and Related Counting Problems
cites work: Approximating convex functions via non-convex oracles under the relative noise model
cites work: A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
cites work: Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
cites work: A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand
cites work: A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs
cites work: On the complexity of energy storage problems
cites work: Approximating the nonlinear newsvendor and single-item stochastic lot-sizing problems when data is given by an oracle
cites work: A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
cites work: Approximating the Permanent
cites work: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
cites work: Pseudorandom generators for polynomial threshold functions
cites work: On the number of Eulerian orientations of a graph
cites work: Faster FPTASes for Counting and Random Generation of Knapsack Solutions
cites work: A deterministic polynomial-time approximation scheme for counting knapsack solutions
cites work: Counting independent sets up to the tree threshold
DOI: 10.1016/J.DAM.2020.05.036
description: scientific article; zbMATH DE number 7395738