论文标题
有效的单方面Kolmogorov近似
Efficient One Sided Kolmogorov Approximation
论文作者
论文摘要
我们提出了一种有效的算法，鉴于离散的随机变量$ x $和一个数字$ m $，它计算一个随机变量，其支持最多为$ m $，并且其kolmogorov距离$ x $的距离也很小，也很小，对于单方面的kolmogorov近似值。我们介绍了算法的一些变体，分析其正确性和计算复杂性，并提供了详细的经验评估，显示它们在实践中的表现。我们检查的主要应用程序是我们进行这项工作的动机，是估计串联平行时间表中缺少截止日期的概率。由于这些概率的精确计算是NP-HARD，因此我们建议使用本文中描述的算法来获得近似值。
We present an efficient algorithm that, given a discrete random variable $X$ and a number $m$, computes a random variable whose support is of size at most $m$ and whose Kolmogorov distance from $X$ is minimal, also for the one-sided Kolmogorov approximation. We present some variants of the algorithm, analyse their correctness and computational complexity, and present a detailed empirical evaluation that shows how they performs in practice. The main application that we examine, which is our motivation for this work, is estimation of the probability missing deadlines in series-parallel schedules. Since exact computation of these probabilities is NP-hard, we propose to use the algorithms described in this paper to obtain an approximation.
