Design and analysis of Algorithms, 2nd Edition

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

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 ...