CSC263H1 Lecture 22: Lecture 22.docx
22 Apr 2014
School
Department
Course
Professor
Document Summary
G: completely connected undirected graph with non-negative weights. Tour of g: a cycle that inclues all nodes og g. A tsp tour: a min-cost tour of g. Tsp problem: given a g, find tsp of g. Brute force algo: find all tours of g, select min_cost one. Bad bcause there are n! tours of g. Worst case : o(n^k) for a constant k. Assume the cost of edges of g satisfy the triangle inequality u,v,w, c(u,v) c(u,w) + c(w,v) Can we solve the triangle-tsp in poly time. But there is a poly-time algo that find a tour of g whose cost is within a constant factor of the optimal tsp tour. Let tsp be an optimal tour of g. Let mst be a minimum spanning tree of g. Remove some edge e of tsp, then we get a spanning tree of g" Triangle-tsp an approx algo: find a mst of g (o(mlogn), do a full walk of mst.
