O'Reilly logo

Design and Analysis of Algorithms by Himanshu B. Dave, Parag H. 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

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

19.1 Introduction

19.2 Randomized Algorithms

19.2.1 Reasons for using Randomized Algorithms

19.2.2 Background—Review of Probability Theory ...

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