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

Get Design and analysis of Algorithms, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.