Chapter 19
Randomized and Approximate Algorithms
Objectives
After reading this chapter, you should understand:
- Ways to get around Intractability: Approximation, Randomness
- The Motivation for Randomized algorithms with some examples
- Randomized Complexity Classes
- The two major classes of Randomized Algorithms
- How to specify an Approximate Algorithm: Ratio Bound
- NP-Hardness of an Approximate Solution: why certain problems are hard to approximate
- The Conditional Expectation Method: a deterministic solution
- How to Analyse Approximation Algorithms through several examples like TSP, GRAPH-3COLOUR
Chapter Outline
Get Design and Analysis of Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
