Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dynamic programming and Approximation Algorithms for NP-Hard Problems -…
Dynamic programming and Approximation Algorithms for NP-Hard Problems
Dynamic programming
It is a technique for solving problems with overlapping
subproblems
Principle of optimality
, It says that an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances
Examples
Coin-row problem
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.
Change-making problem
Give change for amount n using the minimum
number of coins of denominations d1 < d2 < ... < dm.
Coin-collecting problem
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
Top-Down Approach
It leads to an algorithm that solves common
subproblems more than once and hence is very inefficient(typically, exponential or worse)
Bottom Up
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.
Memory
Functions
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
Examples
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∗)
.
Nearest-neighbor algorithm
Multifragment-heuristic algorithm
.
Empirical Results
Local Search Heuristics
Christofides Algorithm
Twice-around-the-tree algorithm
The knapsack Problem
Greedy algorithm for the discrete knapsack problem
Greedy algorithm for the continuous knapsack problem
Approximation Schemes
