Efficient Optimal Approximation of Discrete Random Variables for Estimation of Probabilities of Missing Deadlines
Abstract
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. 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.
Cite
Text
Cohen and Weiss. "Efficient Optimal Approximation of Discrete Random Variables for Estimation of Probabilities of Missing Deadlines." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33017809Markdown
[Cohen and Weiss. "Efficient Optimal Approximation of Discrete Random Variables for Estimation of Probabilities of Missing Deadlines." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/cohen2019aaai-efficient/) doi:10.1609/AAAI.V33I01.33017809BibTeX
@inproceedings{cohen2019aaai-efficient,
title = {{Efficient Optimal Approximation of Discrete Random Variables for Estimation of Probabilities of Missing Deadlines}},
author = {Cohen, Liat and Weiss, Gera},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {7809-7815},
doi = {10.1609/AAAI.V33I01.33017809},
url = {https://mlanthology.org/aaai/2019/cohen2019aaai-efficient/}
}