What’s relaxation?
               f (xA) 1 f (xA) opt 1 f (xA) f (x*)
               opt            opt                opt
                                            x*
                             Min f(x)
                             x in Ω
                                        xA
                  f(x*) < opt = min f(x) < f(xA)
                              x in Ω
                              What’s relaxation?
                                         opt 1/(1 opt  f (xA)) 1/(1 f (x*) f (xA))
                                        f (xA)                    opt                             opt
                                                                                   1/(1   f (x*) f (xA))
                                                                                                  f (x*)
                                                                            x*
                                                  max f(x)
                                                   x in Ω
                                                                     xA
                               f(x*) < opt = max f(x) < f(xA)
                                                     x in Ω
       Traveling Salesman Problem
      (Given a distance table for a complete graph)
        relaxed
     tour        spanning graph  
                   minimum spanning graph 
                       = minimum spanning tree
                   tour 
       add 0.5 opt
        So, the p.r. = 1.5
    Directed TSP with triangular inequality
  (Given a distance table for a complete digraph without loop)
           relaxed
      Directed tour   1-factor (assignment)
                              minimum assignment
                              directed tour
       a directed tour connecting all cycles
       in 1-factor
        TSP in Digraph