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