MM16 - Coggle Diagram
Approximation Algorithms for NP-Hard Problems
Although approximation algorithms run a gamut in level of sophistication, most of them are based on some problem-specific heuristic.
A polynomial-time approximation algorithm is said to be a capproximation algorithm,
Aproximation Algorithms for the Traveling Salesman Problem
Greedy Algorithms for the TSP The simplest approximation algorithms for the
traveling salesman problem are based on the greedy technique.
Minimum-Spanning-Tree–Based Algorithms There are approximation algorithms for the traveling salesman problem that exploit a connection between Hamiltonian circuits and spanning trees of the same graph
Aproximation Algorithms for the Knapsack Problem
Greedy Algorithms for the Knapsack Problem
We can think of several greedy approaches to this problem. One is to select the items in decreasing order of their weights; however, heavier items may not be the most valuable in the set.
Dynamic programming is a technique for solving problems with overlapping
The knapsack Problem and Memory Functions
given n items of known weights w1,...,wn and values v1,...,vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.
The goal is to get a method that solves only subproblems that ar necessary and does so only once. Such a method exists; it is based on using memory functions.
its practicality is limited by dependence on the instance parameters being relatively small.