2014/12/10 by Frod Prefect, Prefect, Frod, Patrick Prosser +1
Computer Science · Decision Sciences · #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #Scheduling and Timetabling Solutions #cs.DS
paper · pdf · doi:10.48550/arxiv.1412.3333
arXiv admin note: text overlap with arXiv:1207.4616
arxiv created 2014/12/10 · arxiv updated 2014/12/11
In an empirical comparisons of algorithms we might compare run times over a set of benchmark problems to decide which one is fastest, i.e. an algorithmic horse race. Ideally we would like to download source code for the algorithms, compile and then run on our machine. Sometimes code isn't available to download and sometimes resource isn't available to implement all the algorithms we want to study. To get round this, published results are rescaled, a technique endorsed by DIMACS, and those rescaled results included in a new study. This technique is frequently used when presenting new algorithms for the maximum clique problem. We demonstrate that this is unsafe, and that if carelessly used may allow us to draw conflicting conclusions from our empirical study.