Estimating the expected cost of function evaluation strategies
Daldal, Rebi and Shahmoradi, Zahed and Ünlüyurt, Tonguç (2019) Estimating the expected cost of function evaluation strategies. In: Global Joint Conference on Industrial Engineering and Its Application Areas (GJCIE 2018), Nevsehir, Turkey
This is the latest version of this item.
Official URL: http://dx.doi.org/10.1007/978-3-030-03317-0_19
We propose a sampling-based method to estimate the expected cost of a given strategy that evaluates a given Boolean function. In general, computing the exact expected cost of a strategy that evaluates a Boolean function obtained by some algorithm may take exponential time. Consequently, it may not be possible to assess the quality of the solutions obtained by different algorithms in an efficient manner. We demonstrate the effectiveness of the estimation method in random instances for algorithms developed for certain functions where the expected cost can be computed in polynomial time. We show that the absolute percentage errors are very small even for samples of moderate size. We propose that in order to compare strategies obtained by different algorithms, it is practically sufficient to compare the estimates when the exact computation of the expected cost is not possible.
Available Versions of this Item
Repository Staff Only: item control page