Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dynamic programming, Approximation algorithm for np hard problems - Coggle…

- - - - 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.
    - - 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.
  - - - 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.
    - - 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.