Beyond the Worst-Case Analysis of Algorithms
by: Tim Roughgarden
Publisher finelybook 出版社: Cambridge University Press; 1st edition (February 25,2021)
Language 语言: English
Print Length 页数: 704 pages
ISBN-10: 1108494315
ISBN-13: 9781108494311
Book Description
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.
Table of contents:
Title Page
Contents
Preface
Contributors
CHAPTER ONE Introduction
PART ONE Refinements of Worse-Case Analysis
CHAPTER TWO Parameterized Algorithms
CHAPTER THREE From Adaptive Analysis to Instance Optimality
CHAPTER FOUR Resource Augmentation
PART TWO Deterministic Models of Data
CHAPTER FIVE Perturbation Resilience
CHAPTER SIX Approximation Stability and Proxy Objectives
CHAPTER SEVEN Sparse Recovery
PART THREE Semirandom Models
CHAPTER EIGHT Distributional Analysis
CHAPTER NINE Introduction to Semirandom Models
CHAPTER TEN Semirandom Stochastic Block Models
CHAPTER ELEVEN Random-Order Models
CHAPTER TWELVE Self-Improving Algorithms
PART FOUR Smoothed Analysis
CHAPTER THIRTEEN Smoothed Analysis of Local Search
CHAPTER FOURTEEN Smoothed Analysis of the Simplex Method
CHAPTER FIFTEEN Smoothed Analysis of Pareto Curves in Multiobjective Optimization
PART FIVE Applications in Machine Learning and Statistics
CHAPTER SIXTEEN Noise in Classification
CHAPTER SEVENTEEN Robust High-Dimensional Statistics
CHAPTER EIGHTEEN Nearest Neighbor Classification and Search
CHAPTER NINETEEN Efficient Tensor Decomposition
CHAPTER TWENTY Topic Models and Nonnegative Matrix Factorization
CHAPTER TWENTY ONE Why Do Local Methods Solve Nonconvex Problems?
CHAPTER TWENTY TWO Generalization in Overparameterized Models
CHAPTER TWENTY THREE Instance Optimal Distribution Testing and Learning
PART SIX Further Applications
CHAPTER TWENTY FOUR Beyond Competitive Analysis
CHAPTER TWENTY FIVE On the Unreasonable Effectiveness of SAT Solvers
CHAPTER TWENTY SIX When Simple Hash Functions Suffice
CHAPTER TWENTY SEVEN Prior-Independent Auctions
CHAPTER TWENTY EIGHT Distribution-Free Models of Social Networks
CHAPTER TWENTY NINE Data-Driven Algorithm Design
CHAPTER THIRTY Algorithms with Predictions
Index
此内容查看价格为4积分（VIP免费），请先登录
Beyond the Worst-Case Analysis of Algorithms 9781108494311.zip
