## Estimating the expected cost of function evaluation strategiesDaldal, Rebi and Shahmoradi, Zahed and Ünlüyurt, Tonguç (2019)
Official URL: http://dx.doi.org/10.1007/978-3-030-03317-0_19 ## AbstractWe 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- Estimating the expected cost of function evaluation strategies. (deposited 13 Aug 2018 15:57)
- Estimating the expected cost of function evaluation strategies. (deposited 29 Jul 2019 14:55)
**[Currently Displayed]**
- Estimating the expected cost of function evaluation strategies. (deposited 29 Jul 2019 14:55)
Repository Staff Only: item control page |