Faster FPTASes for counting and random generation of knapsack solutions

DOI10.1007/978-3-662-44777-2_63MaRDI QIDQ2921460zbMATH OpenOpenAlexFDO

Authors Romeo Rizzi, Alexandru I. Tomescu

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2347, http://hdl.handle.net/10138/302575

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Dynamic programming (90C39)

Abstract: Given a combinatorial decomposition for a counting problem, we resort to the simple scheme of approximating large numbers by floating-point representations in order to obtain efficient Fully Polynomial Time Approximation Schemes (FPTASes) for it. The number of bits employed for the exponent and the mantissa will depend on the error parameter $0<varepsilonleq1$ and on the characteristics of the problem. Accordingly, we propose the first FPTASes with $1pmvarepsilon$ relative error for counting and generating uniformly at random a labeled DAG with a given number of vertices. This is accomplished starting from a classical recurrence for counting DAGs, whose values we approximate by floating-point numbers. After extending these results to other families of DAGs, we show how the same approach works also with problems where we are given a compact representation of a combinatorial ensemble and we are asked to count and sample elements from it. We employ here the floating-point approximation method to transform the classic pseudo-polynomial algorithm for counting 0/1 Knapsack solutions into a very simple FPTAS with $1-varepsilon$ relative error. Its complexity improves upon the recent result (v{S}tefankoviv{c} et al., SIAM J. Comput., 2012), and, when $varepsilo{n}^{-1}=Omega(n)$, also upon the best-known randomized algorithm (Dyer, STOC, 2003). To show the versatility of this technique, we also apply it to a recent generalization of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG, obtaining a faster and simpler FPTAS than the existing one.

Recommendations

• Faster FPTASes for counting and random generation of knapsack solutions
• A faster FPTAS for \#Knapsack
• Approximate counting by dynamic programming
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy

Cited in

(8)

• A faster FPTAS for counting two-rowed contingency tables
• Faster FPTASes for counting and random generation of knapsack solutions
• An FPTAS for the volume computationof 0-1 knapsack polytopes based on approximate convolution integral
• A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
• Approximate counting by dynamic programming
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• A faster FPTAS for \#Knapsack
• A faster FPTAS for knapsack problem with cardinality constraint

This page was built for publication: Faster FPTASes for counting and random generation of knapsack solutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921460)