MM16

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.

Approximation Algorithms for NP-Hard Problems

its practicality is limited by dependence on the instance parameters being relatively small.

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