TY - JOUR
AU - Cohen, Liat
AU - Weiss, Gera
PY - 2019/07/17
Y2 - 2022/12/03
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 -