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

Get Design and Analysis of Algorithms now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.