Empirical scaling analyzer: An automated system for empirical analysis of performance scaling

Article type: Research Article

Authors: Pushak, Yasha^a | Mu, Zongxu^a | Hoos, Holger H.^{a; b; *}

Affiliations: [a] Department of Computer Science, The University of British Columbia, BC, Canada. E-mails: [email protected], [email protected], [email protected] | [b] LIACS, Universiteit Leiden, The Netherlands

Correspondence: [*] Corresponding author. E-mail: [email protected].

Abstract: The time complexity of algorithms, i.e., the scaling of the time required for solving a problem instance as a function of instance size, is of key interest in theoretical computer science and practical applications. In this work, we present a fully automated tool – Empirical Scaling Analyzer (ESA) – for performing sophisticated and detailed empirical scaling analyses. The methodological approach underlying ESA is based on a combination of automatic function fitting and bootstrap sampling; previous versions of the methodology have been used in prior work to characterize the empirical scaling behaviour of several prominent, high-performance SAT and TSP solvers. ESA is applicable to any algorithm or system, as long as running time data can be collected on sets of problem instances of various sizes. We present results from rigorous stress-testing to critically assess ESA on scenarios with challenging characteristics. We also give an overview of empirical scaling results obtained using ESA.

Keywords: Empirical scaling analysis, running time scaling

DOI: 10.3233/AIC-200630

Journal: AI Communications, vol. 33, no. 2, pp. 93-111, 2020