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
computer science
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
