Please enable JavaScript.
Coggle requires JavaScript to display documents.
M16-2 - Coggle Diagram
M16-2
Approximation Algorithm for NP-Hard Problems
A heuristic is a common-sense rule drawn from experience rather than from a mathematically proved assertion. For example, going to the nearest unvisited city in the traveling
salesman problem is a good illustration of this notion.
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.
The best (i.e., the smallest) value of c for which inequality (12.3) holds for all instances of the problem is called the performance ratio of the algorithm and denoted RA.
Approximation Algorithm for Traveling Salesman Problem
Greedy Algorithms for the TSP: The simplest approximation algorithms for the
traveling salesman problem are based on the greedy technique. We will discuss here two such algorithms.
Multifragment-heuristic algorithm
Another natural greedy algorithm for the traveling salesman problem considers it as the problem of finding a minimum-weight collection of edges in a given complete weighted graph so that all the vertices have degree 2.
Step 2: Repeat this step n times, where n is the number of cities in the instance being solved: add the next edge on the sorted edge list to the set of tour edges, provided this addition does not create a vertex of degree 3 or a cycle of length less than n; otherwise, skip the edge.
Step 3: Return the set of tour edges.
Step 1: Sort the edges in increasing order of their weights. (Ties can be broken arbitrarily.) Initialize the set of tour edges to be constructed to the empty set.
Nearest-neighbor algorithm
The following well-known greedy algorithm is based on the nearest-neighbor heuristic: always go next to the nearest unvisited city.
Step 2: Repeat the following operation until all the cities have been visited: go to the unvisited city nearest the one visited last.
Step 3: Return to the starting city.
Step 1: Choose an arbitrary city as the start.
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. Since removing an edge from
a Hamiltonian circuit yields a spanning tree, we can expect that the structure of a minimum spanning tree provides a good basis for constructing a shortest tour approximation..
Twice-around-the-tree algorithm
Step 2: Starting at an arbitrary vertex, perform a walk around the minimum spanning tree recording all the vertices passed by. (This can be done by a DFS traversal.)
Step 3: Scan the vertex list obtained in Step 2 and eliminate from it all repeated occurrences of the same vertex except the starting one at the end of the list. (This step is equivalent to making shortcuts in the walk.) The vertices remaining on the list will form a Hamiltonian circuit, which is the output of the algorithm.
Step 1: Construct a minimum spanning tree of the graph corresponding to a given instance of the traveling salesman problem.
Chistofides Algorithm
It also uses a minimum spanning tree but does this in a more sophisticated way than the twice-around-the-tree algorithm. Note
that a twice-around-the-tree walk generated by the latter algorithm is an Eulerian circuit in the multigraph obtained by doubling every edge in the graph given.
Recall that an Eulerian circuit exists in a connected multigraph if and only if all its vertices have even degrees. The Christofides algorithm obtains such a multi-graph by adding to the graph the edges of a minimum-weight matching of all the odd-degree vertices in its minimum spanning tree. (The number of such vertices is always even and hence this can always be done.)
1 more item...
Local-Search Heuristics
For Euclidean instances, surprisingly good approximations to optimal tours can be obtained by iterative-improvement algorithms, which are also called local search heuristics.
These algorithms start with some initial tour, e.g., constructed randomly or by some simpler approximation algorithm such as the nearest-neighbor. On each iteration, the algorithm explores a neighborhood around the current tour by replacing a few edgess in the current tour by other edges. If the changes produce a shorter tour, the algorithm makes it the current tour and continues by exploring its neighborhood in the same manner; otherwise,
the current tour is returned as the algorithm’s output and the algorithm stops.
2 more items...
Approximation Algorithm for the Knapsack Problem
Greedy Algorithms for the Knapsack Problem:
Greedy algorithm for the continuous knapsack problem
Step 2: Sort the items in nonincreasing order of the ratios computed in Step 1. (Ties can be broken arbitrarily.)
Step 3: Repeat the following operation until the knapsack is filled to its full capacity or no item is left in the sorted list: if the current item on the list fits into the knapsack in its entirety, take it and proceed to the next item; otherwise, take its largest fraction to fill the knapsack to its full capacity and stop.
Step 1: Compute the value-to-weight ratios vi/wi, i = 1, . . . , n, for the items given.
Greedy algorithm for the discrete knapsack problem
Step 2: Sort the items in nonincreasing order of the ratios computed in Step 1. (Ties can be broken arbitrarily.)
Step 3: Repeat the following operation until no item is left in the sorted list: if the current item on the list fits into the knapsack, place it in the knapsack and proceed to the next item; otherwise, just proceed to the next item.
Step 1: Compute the value-to-weight ratios ri = vi/wi, i = 1, . . . , n, for the items given.