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.

[thumbnail of gjcie2018_estimation.docx] MS Word
gjcie2018_estimation.docx

Download (8MB)

Abstract

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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Tonguç Ünlüyurt
Date Deposited: 29 Jul 2019 14:55
Last Modified: 26 Apr 2022 09:33
URI: https://research.sabanciuniv.edu/id/eprint/38467

Available Versions of this Item

Actions (login required)

View Item
View Item