O'Reilly logo

Design and analysis of Algorithms, 2nd Edition by Himanshu B Dave

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required