Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dynamic Programming, Approximation Algorithms for NP-Hard Problems -…

- - - - 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. The best-known of these are the 2-opt, 3- opt, and Lin-Kernighan algorithms. 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 edges 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.
        
        Approximation 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. Alternatively, if we pick up the items in decreasing order of their value, there is no guarantee that the knapsack’s capacity will be used efficiently. Can we find a greedy strategy that takes into account both the weights and values? Yes, we can, by computing the value-to-weight ratios vi/wi, i = 1, 2, . . . , n, and selecting the items in decreasing order of these ratios. (In fact, we already used this approach in designing the branch-and-bound algorithm for the problem in Section 12.2.) Here is the algorithm based on this greedy heuristic.
        
        Greedy algorithm for the discrete knapsack problem :Step 1 Compute the value-to-weight ratios ri = vi/wi, i = 1, . . . , n, for the items given. 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.
        
        Greedy algorithm for the continuous knapsack problem: Step 1 Compute the value-to-weight ratios vi/wi, i = 1, . . . , n, for the items given. 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.
        
        Approximation Schemes :We now return to the discrete version of the knapsack problem. For this problem, unlike the traveling salesman problem, there exist polynomial-time approximation schemes, which are parametric families of algorithms that allow us to get approximations sa^(k) with any predefined accuracy level:f (s∗)/f(sa^(k)) ≤ 1 + 1/k for any instance of size n, where k is an integer parameter in the range 0 ≤ k < n. The first approximation scheme was suggested by S. Sahni in 1975. This algorithm generates all subsets of k items or less, and for each one that fits into the knapsack it adds the remaining items as the greedy algorithm would do (i.e., in nonincreasing order of their value-to-weight ratios). The subset of the highest value obtained in this fashion is returned as the algorithm’s output.
- - - - Step 1 Choose an arbitrary city as the start. Step 2 Repeat the following operation until all the cities have been visited:go to the unvisited city nearest the one visited last (ties can be broken arbitrarily). Step 3 Return to the starting city. The optimal solution, as can be easily checked by exhaustive search, is the tour s∗: a − b − d − c − a of length 8. Thus, the accuracy ratio of this approximation is r(sa) = f (sa)/f (s∗) = 10/8 = 1.25 (i.e., tour sa is 25% longer than the optimal tour s∗)
        
        Unfortunately, except for its simplicity, not many good things can be said about the nearest-neighbor algorithm.
    - - 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. 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.
        
        In general, the multifragment-heuristic algorithm tends to produce significantly better tours than the nearest-neighbor algorithm, as we are going to see from the experimental data quoted at the end of this section. But the performance ratio of the multifragment-heuristic algorithm is also unbounded, of course