2018/06/26 by Tim Roughgarden, Roughgarden, Tim · 1 voice · 1 citation
Computer Science · #Distributed and Parallel Computing Systems #IoT and Edge/Fog Computing #Machine Learning in Healthcare #cs.DS
paper · pdf · doi:10.48550/arxiv.1806.09817
To appear in Communications of the ACM
arxiv created 2018/06/26 · openalex publication_date 2018/06/26 · arxiv updated 2018/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the worst-case analysis of algorithms, the overall performance of an algorithm is summarized by its worst performance on any input. This approach has countless success stories, but there are also important computational problems --- like linear programming, clustering, online caching, and neural network training --- where the worst-case analysis framework does not provide any helpful advice on how to solve the problem. This article covers a number of modeling methods for going beyond worst-case analysis and articulating which inputs are the most relevant.