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.

[img]MS Word

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.

Item Type:Papers in Conference Proceedings
ID Code:38467
Deposited By:Tonguç Ünlüyurt
Deposited On:29 Jul 2019 14:55
Last Modified:29 Jul 2019 14:55

Available Versions of this Item

Repository Staff Only: item control page