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 … Read more

New Benchmark Instances for the Steiner Problem in Graphs

We propose in this work 50 new test instances for the Steiner problem in graphs. These instances are characterized by large integrality gaps and symmetry aspects which make them harder to both exact methods and heuristics than the test problems currently in use for the evaluation and comparison of existing and newly developed algorithms. Our … Read more