Real-life Examples
Food Delivery
Find an itinerary to deliver goods from sources to destinations in the smallest possible time. (Traveling Salesman Problem)
Viral Marketing
Distribute free samples to influential users of a social network s.t. the number of followers that see the sample is maximum.
Job Scheduling
Find an assignment of jobs to machines in such a way that the overall completion time is minimum.
Optimization Problem
- Input
- A set of feasible solutions
- A value for each solution
Compute the best solution according to its value (optimum).
Minimization: Compute a solution with minimum value (cost).
Maximization: Compute a solution with maximum value (revenue).
Intractability
Unfortunately, many optimization problems are \(NP\)-hard.
Unless \(P=NP\), we cannot devise efficient (polynomial time) algorithms to find optimal solutions to such problems that at the same time:
- Find optimal solutions;
- In polynomial-time;
- For any instances.
Options:
- 1+2: Find solutions for special cases
- 1+3: Find solutions in long computational time
- 2+3: Find approximate solutions
Approximation Algorithms
We will not seek for optimal solutions, we aim at finding algorithms that
- Run in polynomial time.
- For each instance, solutions found are guaranteed to be close to the optimal solution within some bound.
Approximation Factor
An \(\alpha\)-approximation algorithm for an optimization problem is a polynomial-time algorithm that for all instances of the problem produces a solution whose value is within an factor of \(\alpha\) of the value of an optimal solution.
\(\alpha\): performance guarantee, approximation factor, or approximation ratio.
For minimization problem: \(\alpha>1\).
For maximization problem \(\alpha<1\).
Observations:
- The approximation factor bounds are due to worst case analysis.
- Most of the times the approximation factors are better in practice.
- We can find approximation also for problems that can be solved in polynomial time.