Profile Picture

Dr. Franc Brglez

Visiting Research Professor

Research

In 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:

  • On Asymptotic Performance of Combinatorial Solvers:
    a Picture that Replaces a Thousand Tables
  • On Markov Chain Data Structures, Self-Avoiding Walks,
    and Cover Time in Very Large Sparse Graphs
  • On Stochastic Combinatorial Optimization and Markov Chains:
    from Walks with Self-Loops to Self-Avoiding Walks

    Research Areas

    • Stochastic combinatorial optimization
    • Experimental design for rigorous performance testing of algorithms
    • Experimental algorithmics and analytics