Beyond worst-case analysis
| Autor: | Tim Roughgarden |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science Artificial neural network Linear programming business.industry Computer science 0102 computer and information sciences 02 engineering and technology Machine learning computer.software_genre 01 natural sciences 010201 computation theory & mathematics Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) 020201 artificial intelligence & image processing Overall performance Artificial intelligence Computational problem Cluster analysis business computer Advice (complexity) Case analysis Analysis of algorithms |
| Zdroj: | Communications of the ACM. 62:88-96 |
| ISSN: | 1557-7317 0001-0782 |
| DOI: | 10.1145/3232535 |
| Popis: | 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. To appear in Communications of the ACM |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|