Atlas home || Conferences | Abstracts | about Atlas

SCRA 2006-FIM XIII-Thirteenth International Conference of the Forum for Interdisciplinary Mathematics on Interdisciplinary Mathematical and Statistical Techniques
September 1-4, 2006
New University of Lisbon-Tomar Polytechnic Institute
Lisbon-Tomar, Portugal

Organizers
Sat Gupta, Carlos Coelho and Satya Mishra

View Abstracts
Conference Homepage

Modeling computing costs with search trees
by
Alda Carvalho
ISEL and CEMAPRE
Coauthors: Nuno Crato, ISEG and CEMAPRE, ncrato@iseg.utl.pt Carla Gomes, Cornell University

The runtime distributions of several combinatorial problems have been shown to exhibit heavy-tailed behavior. We show how normalized sums of exponentials and mixtures of stable distributions adequately model such runtime distributions. We also discuss simple tree search models that simulate the behavior of some algorithms and generate heavy tailed behavior, similar to the one found in empirical studies.

Date received: June 30, 2006

Copyright © 2006 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # casn-84.