Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM16 - Coggle Diagram
MM16
Approximation Algorithms for NP-Hard Problems
branch-and-bound technique
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.
Multifragment-heuristic algorithm
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
Christofides Algorithm
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.
Approximation Schemes
Dynamic Programming
Dynamic programming is a technique for solving problems with overlapping
subproblems.
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.
Memory Functions
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.