Dynamic programming and Approximation Algorithms for NP-Hard Problems -…
Dynamic programming and Approximation Algorithms for NP-Hard Problems
It is a technique for solving problems with overlapping
Principle of optimality
, It says that an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances
There is a row of n coins whose values are some
positive integers c1, c2,...,cn, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up.
Give change for amount n using the minimum
number of coins of denominations d1 < d2 < ... < dm.
Several coins are placed in cells of an
n × m board, no more than one coin per cell. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right
or one cell down from its current location. When the robot visits a cell with a coin, it always picks up that coin. Find the maximum number of coins the robot can collect and a path it needs to follow to do this.
The Knapsack Problem
It leads to an algorithm that solves common
subproblems more than once and hence is very inefficient(typically, exponential or worse)
It fills a table with solutions to all smaller subproblems, but each of them is solved only once. An unsatisfying aspect of this approach is that solutions to some of these smaller subproblems are often not necessary for getting a solution
to the problem given.
This method solves a given problem in the top-down manner but, in addition, maintains a table of the kind that would have been used by a bottom-up dynamic programming algorithm.
Approximation Algorithms for NP-Hard Problems
We can quantify the accuracy of an approximate solution sa to a problem of minimizing some function f by the size of the relative error of this approximation
The closer r(sa) is to 1, the better the approximate solution is
A polynomial-time approximation algorithm is said to be a c approximation algorithm, where c ≥ 1, if the accuracy ratio of the approximation it produces does not exceed c for any instance of the problem in question: r(sa) ≤ c
Traveling salesman Problem
If P != NP, there exists no c-approximation algorithm for the
traveling salesman problem, i.e., there exists no polynomial-time approximation algorithm for this problem so that for all instances
f (sa) ≤ cf (s∗)
Local Search Heuristics
The knapsack Problem
Greedy algorithm for the discrete knapsack problem
Greedy algorithm for the continuous knapsack problem