ResearchIn 1953, Metropolis introduced well-defined criteria for the next step of a random walk on vertices of a graph, with vertices represented as 'states'. Since then, new randomized search heuristics continue to evolve with examples of solutions to a wide range of combinatorial optimization problems. Metaphors from physics (simulated annealing heuristic) are increasingly augmented with heuristics that are inspired by metaphors from nature (behaviors of ants, bats, bees, bird flocks, cuckoos, …), while alternative approaches continue under the framework of markov chains.
In my view, experiments that compare runtime performance of algorithms based on
metaphors from nature have led to inconclusive results all too frequently.
Our experiments point to two dominating factors that can lead to such results:
(1) problem instances may be "too easy";
(2) statistical tests include too many censored observations.
We emphasize the significance of these factors in the articles
listed under the
Publications header above.
The common threads for each of these articles are:
(1) problem instances are hard and only get harder as the instance size increases;
(2) statistical tests are based strictly on uncensored observations.
I will elaborate on additional findings in my research in the three articles in the making:
a Picture that Replaces a Thousand Tables
and Cover Time in Very Large Sparse Graphs
from Walks with Self-Loops to Self-Avoiding Walks
- Stochastic combinatorial optimization
- Experimental design for rigorous performance testing of algorithms
- Experimental algorithmics and analytics