Description

Approximation algorithms: introduction 

Coping with NP-hardness-hard problem: unlikely to have an algorithm that always produces correct answer and runs in polynomial time even in worst case In practice, -hard problems need to be solved all the time We can relax correctness as well as worst case conditions: 

• Modify the problem: change objective, restrict inputs, change input model, … 

• Relax correctness condition: allow approximate answers.

Algorithm that gives a near-optimal solution is called approximation algorithm.

In complexity theory we focused on decision problems (yes/no answers) 

In approximation algorithms we focus on optimization problems: maximize or minimize a given objective function