Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms
Run time distributions or time-to-target plots are very useful tools to characterize the running times of stochastic algorithms for combinatorial optimization. We further explore run time distributions and describe a new tool to compare two algorithms based on stochastic local search. For the case where the running times of both algorithms fit exponential distributions, we derive a closed form index that gives the probability that one of them finds a solution at least as good as a given target value in a smaller computation time than the other. This result is extended to the case of general run time distributions and a numerical iterative procedure is described for the computation of the above probability value. Numerical examples illustrate the application of this tool in the comparison of different sequential and parallel algorithms for a number of distinct problems. Copyright Springer Science+Business Media, LLC. 2012
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Volume (Year): 54 (2012)
Issue (Month): 2 (October)
|Contact details of provider:|| Web page: http://www.springer.com/business/operations+research/journal/10898|
|Order Information:||Web: http://link.springer.de/orders.htm|
When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:54:y:2012:i:2:p:405-429. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla)or (Christopher F Baum)
If references are entirely missing, you can add them using this form.