Efficient One Sided Kolmogorov Approximation
This work addresses the need for efficient approximations in probabilistic scheduling, which is incremental as it builds on existing Kolmogorov distance methods for a specific domain.
The paper tackles the problem of approximating a discrete random variable with minimal Kolmogorov distance using a support of size at most m, including one-sided variants, and presents algorithms with empirical evaluation, showing practical performance in applications like estimating deadline miss probabilities in NP-hard scheduling problems.
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.