Beyond the Worst-Case Analysis of Algorithms

By: Roughgarden,Tim (Ed.)Language: English Publication details: Cambridge Cambridge University Press 2021Description: xvii, 686pISBN: 9781108494311 (HB)Subject(s): Computer programming | Computer algorithms | Computing | Computer Science
Contents:
1. Introduction 2. Parameterized algorithms 3. From adaptive analysis to instance optimality 4. Resource augmentation 5. Perturbation resilience 6. Approximation stability and proxy objectives 7. Sparse recovery 8. Distributional analysis 9. Introduction to semi-random models 10. Semi-random stochastic block models 11. Random-order models 12. Self-improving algorithms 13. Smoothed analysis of local search 14. Smoothed analysis of the simplex method 15. Smoothed analysis of Pareto curves in multiobjective optimization 16. Noise in classification 17. Robust high-dimensional statistics 18. Nearest-neighbor classification and search 19. Efficient tensor decomposition 20. Topic models and nonnegative matrix factorization 21. Why do local methods solve nonconvex problems? 22. Generalization in overparameterized models 23. Instance-optimal distribution testing and learning 24. Beyond competitive analysis 25. On the unreasonable effectiveness of satisfiability solvers 26. When simple hash functions suffice 27. Prior-independent auctions 28. Distribution-free models of social networks 29. Data-driven algorithm design 30. Algorithms with predictions
Summary: There are no silver bullets in algorithm design, and no single algorithmic idea is powerful and flexible enough to solve every computational problem. Nor are there silver bullets in algorithm analysis, as the most enlightening method for analyzing an algorithm often depends on the problem and the application. However, typical algorithms courses rely almost entirely on a single analysis framework, that of worst-case analysis, wherein an algorithm is assessed by its worst performance on any input of a given size. The purpose of this book is to popularize several alternatives to worst-case analysis and their most notable algorithmic applications, from clustering to linear programming to neural network training. Forty leading researchers have contributed introductions to different facets of this field, emphasizing the most important models and results, many of which can be taught in lectures to beginning graduate students in theoretical computer science and machine learning.
Item type: BOOKS List(s) this item appears in: New Arrivals (03 July, 2024)
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Current library Home library Call number Materials specified Status Notes Date due Barcode
IMSc Library
IMSc Library
681.3 ROU (Browse shelf (Opens below)) Not for loan New Arrivals Displayed Till 18 July 2024 78040

Includes Index

1. Introduction
2. Parameterized algorithms
3. From adaptive analysis to instance optimality
4. Resource augmentation
5. Perturbation resilience
6. Approximation stability and proxy objectives
7. Sparse recovery
8. Distributional analysis
9. Introduction to semi-random models
10. Semi-random stochastic block models
11. Random-order models
12. Self-improving algorithms
13. Smoothed analysis of local search
14. Smoothed analysis of the simplex method
15. Smoothed analysis of Pareto curves in multiobjective optimization
16. Noise in classification
17. Robust high-dimensional statistics
18. Nearest-neighbor classification and search
19. Efficient tensor decomposition
20. Topic models and nonnegative matrix factorization
21. Why do local methods solve nonconvex problems?
22. Generalization in overparameterized models
23. Instance-optimal distribution testing and learning
24. Beyond competitive analysis
25. On the unreasonable effectiveness of satisfiability solvers
26. When simple hash functions suffice
27. Prior-independent auctions
28. Distribution-free models of social networks
29. Data-driven algorithm design
30. Algorithms with predictions

There are no silver bullets in algorithm design, and no single algorithmic idea is powerful and flexible enough to solve every computational problem. Nor are there silver bullets in algorithm analysis, as the most enlightening method for analyzing an algorithm often depends on the problem and the application. However, typical algorithms courses rely almost entirely on a single analysis framework, that of worst-case analysis, wherein an algorithm is assessed by its worst performance on any input of a given size. The purpose of this book is to popularize several alternatives to worst-case analysis and their most notable algorithmic applications, from clustering to linear programming to neural network training. Forty leading researchers have contributed introductions to different facets of this field, emphasizing the most important models and results, many of which can be taught in lectures to beginning graduate students in theoretical computer science and machine learning.

There are no comments on this title.

to post a comment.
The Institute of Mathematical Sciences, Chennai, India

Powered by Koha