Approximation Algorithm problem (a) (5 points) Suppose Professor Selden discover

Question

Approximation Algorithm problem

(a) (5 points) Suppose Professor Selden discovers an algorithm for the Traveling Salesman Problem that always produces a tour whose length is at most 10 times the length of the optimal tour, for any set of inter-city distances, even if they do not satisfy the triangle inequality. Has the professor proved that P NP? xplain your answer Suppose we want to find the maximum weight spanning tree of a weighted undirected graph G J (V, E,w). Assume every edge has a unique weight. (b) (2 points) o solution is to negate the edge weights and then apply s algorithm ne What is the running time of this approach? The rest of the problem focuses on how to solve an approximate version of the problem more efficiently. Let S be the subset of E consisting of the maximum weight edge incident on each vertex (that is, for each vertex v, find the maximum weight edge incident on v and add it to S). (c) (4 points) Draw a graph consisting of four vertices forming a cycle and assign the edge weights {1, 2, 3, 4) in such a way that the maximum weight spanning tree of the graph consists exactly of the edges in S.

Explanation / Answer

According to chegg policy I will be answering only 1 question. Post others separately.

a) No, Prof has not solved any NP-complete problem in polynomial time. He has just given a solution to different version (Approximation version) which is not NP-complete.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.