An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths

DOI10.1007/978-3-319-53925-6_33zbMath1485.68308OpenAlexW2588896144MaRDI QIDQ2980930

Ei Ando

Publication date: 5 May 2017

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-53925-6_33

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• A geometric inequality and the complexity of computing volume
• Computing the volume is difficult
• A fully polynomial-time approximation scheme for approximating a sum of random variables
• Directed tree-width
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
• Bypassing KLS
• Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG
• On the Complexity of Computing the Volume of a Polyhedron
• A random polynomial-time algorithm for approximating the volume of convex bodies
• An FPTAS for #Knapsack and Related Counting Problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths