TY - JOUR AU - Cohen, Liat AU - Weiss, Gera PY - 2019/07/17 Y2 - 2024/03/29 TI - Efficient Optimal Approximation of Discrete Random Variables for Estimation of Probabilities of Missing Deadlines JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Reasoning under Uncertainty DO - 10.1609/aaai.v33i01.33017809 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4778 SP - 7809-7815 AB - <p>We present an efficient algorithm that, given a discrete random variable <em>X</em> and a number <em>m</em>, computes a random variable whose support is of size at most <em>m</em> and whose Kolmogorov distance from <em>X</em> is minimal. 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 of 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.</p> ER -