Please enable JavaScript.

Coggle requires JavaScript to display documents.

Aproximation Algorithms for NP-Hard Problems - Coggle Diagram

- - - - The performance ratio serves as the principal metric indicating the quality of the approximation algorithm
- - - - Nearest-neighbor algorithm
        
        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.
      - Multifragment-heuristic algorithm
        
        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.
  - - - 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.