Beyond the Worst-Case Analysis of Algorithms
$71.99 (C)
- Editor: Tim Roughgarden, Columbia University, New York
- Date Published: February 2021
- availability: Available
- format: Hardback
- isbn: 9781108494311
$
71.99
(C)
Hardback
Other available formats:
eBook
Looking for an examination copy?
If you are interested in the title for your course we can consider offering an examination copy. To register your interest please contact [email protected] providing details of the course you are teaching.
-
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.
Read more- Most chapters include open research directions and exercises suitable for classroom use
- First time this exciting research area has been covered by a book
- Many applications, especially in machine learning
Reviews & endorsements
'Many important algorithmic problems are considered intractable according to the conventional worst-case metrics of computational complexity theory. This important book demonstrates that, for many such problems, it is possible to craft algorithms that perform well under plausible assumptions about the structure of the inputs that are likely to be presented. It may well mark a turning point in the field of algorithm design and analysis.' Richard M. Karp, University of California at Berkeley
See more reviews'The worst-case analysis sets a criteria for perfect algorithmic performance. It has led and will continue to lead to the creation of breakthrough algorithms unthinkable by previous generations. But the success of worst-case analysis as the main theoretical computing framework has also placed provably-good algorithm design in a quandary, because nearly all practically significant problems have been shown to be intractable under such perfect criteria. Going beyond the worst-case analysis is a much-needed step for the theory of computing. This book - broad in scope and united by a common theme - represents diverse efforts in the field, and will elevate this fundamental subject for connecting computing theory with the rapid advances in Big Data and AI Solutions.' Shanghua Teng, University of Southern California
‘The book is a must have for any aspiring algorithm researcher … Essential.’ D. Papamichail, Choice Magazine
Customer reviews
Not yet reviewed
Be the first to review
Review was not posted due to profanity
×Product details
- Date Published: February 2021
- format: Hardback
- isbn: 9781108494311
- length: 704 pages
- dimensions: 260 x 188 x 40 mm
- weight: 1.4kg
- availability: Available
Table of Contents
Forward
Preface
1. Introduction Tim Roughgarden
Part I. Refinements of Worst-Case Analysis:
2. Parameterized algorithms Fedor Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi
3. From adaptive analysis to instance optimality Jérémy Barbay
4. Resource augmentation Tim Roughgarden
Part II. Deterministic Models of Data:
5. Perturbation resilience Konstantin Makarychev and Yury Makarychev
6. Approximation stability and proxy objectives Avrim Blum
7. Sparse recovery Eric Price
Part III. Semi-Random Models:
8. Distributional analysis Tim Roughgarden
9. Introduction to semi-random models Uriel Feige
10. Semi-random stochastic block models Ankur Moitra
11. Random-order models Anupam Gupta and Sahil Singla
12. Self-improving algorithms C. Seshadhri
Part IV. Smoothed Analysis:
13. Smoothed analysis of local search Bodo Manthey
14. Smoothed analysis of the simplex method Daniel Dadush and Sophie Huiberts
15. Smoothed analysis of Pareto curves in multiobjective optimization Heiko Röglin
Part V. Applications in Machine Learning and Statistics:
16. Noise in classification Maria-Florina Balcan and Nika Haghtalab
17. Robust high-dimensional statistics Ilias Diakonikolas and Daniel Kane
18. Nearest-neighbor classification and search Sanjoy Dasgupta and Samory Kpotufe
19. Efficient tensor decomposition Aravindan Vijayaraghavan
20. Topic models and nonnegative matrix factorization Rong Ge and Ankur Moitra
21. Why do local methods solve nonconvex problems? Tengyu Ma
22. Generalization in overparameterized models Moritz Hardt
23. Instance-optimal distribution testing and learning Gregory Valiant and Paul Valiant
Part VI. Further Applications:
24. Beyond competitive analysis Anna R. Karlin and Elias Koutsoupias
25. On the unreasonable effectiveness of satisfiability solvers Vijay Ganesh and Moshe Vardi
26. When simple hash functions suffice Kai-Min Chung, Michael Mitzenmacher and Salil Vadhan
27. Prior-independent auctions Inbal Talgam-Cohen
28. Distribution-free models of social networks Tim Roughgarden and C. Seshadhri
29. Data-driven algorithm design Maria-Florina Balcan
30. Algorithms with predictions Michael Mitzenmacher and Sergei Vassilvitskii.-
Resources for
Beyond the Worst-Case Analysis of Algorithms
General Resources
Find resources associated with this title
Type Name Unlocked * Format Size Showing of
This title is supported by one or more locked resources. Access to locked resources is granted exclusively by Cambridge University Press to instructors whose faculty status has been verified. To gain access to locked resources, instructors should sign in to or register for a Cambridge user account.
Please use locked resources responsibly and exercise your professional discretion when choosing how you share these materials with your students. Other instructors may wish to use locked resources for assessment purposes and their usefulness is undermined when the source files (for example, solution manuals or test banks) are shared online or via social networks.
Supplementary resources are subject to copyright. Instructors are permitted to view, print or download these resources for use in their teaching, but may not change them or use them for commercial gain.
If you are having problems accessing these resources please contact [email protected].
Related Books
related journals
also by this author
Sorry, this resource is locked
Please register or sign in to request access. If you are having problems accessing these resources please email [email protected]
Register Sign in» Proceed
You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner www.ebooks.com. Please see the permission section of the www.ebooks.com catalogue page for details of the print & copy limits on our eBooks.
Continue ×Are you sure you want to delete your account?
This cannot be undone.
Thank you for your feedback which will help us improve our service.
If you requested a response, we will make sure to get back to you shortly.
×