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
There’s no sense being exact about something if you don’t even know what you’re talking about.
—John von Neumann
I have not failed. I’ve just found 10,000 ...