A minimum cost spanning tree of the graph

Reference no: EM131121782

Christofides' Traveling Salesman Heuristic) Consider a symmetric traveling salesman problem where the arc costs are nonnegative and satisfy the triangle inequality (cf. the preceding exercise). Let R be a minimum cost spanning tree of the graph and let S be the subset of the nodes that has an odd number of incident arcs in R. A perfect matching of the nodes of S is a subset of arcs such that every node of S is an end node of exactly one arc of the subset and each arc of the subset has end nodes in S. Suppose that M is a perfect matching of the nodes of S that has minimum sum of arc costs. Construct a tour that consists of the arcs of M and some of the arcs of R, and show that its weight is no more than 3/2 times the optimal tour cost. Solve the problem of Fig. 10.18 using this heuristic, and find the ratio of the solution cost to the optimal tour cost.

Reference no: EM131121782

Questions Cloud

Describe the concept of it governance and control objectives : Describe the concepts of IT governance and control objectives for information and related technology (COBIT) and discuss how these concepts apply to an effective information systems audit.

Degree-constrained minimum weight spanning trees : (Degree-Constrained Minimum Weight Spanning Trees) Consider the minimum weight spanning tree problem, subject to the additional constraint that the number of tree arcs that are incident to a single given node s should be no greater than a given in..

The version of the traveling salesman problem : (K-Traveling Salesmen Problem) Consider the version of the traveling salesman problem where there are K salesmen that start at city 1, return to city 1, and collectively must visit all other cities exactly once. Transform the problem into an ordin..

Explain how these organizations can benefit you : Explain elements or attributes of these organizations that appeal to you most and you find the most useful. For one of your chosen organizations, explain which elements or attributes are geared toward IT leaders.

A minimum cost spanning tree of the graph : Christofides' Traveling Salesman Heuristic) Consider a symmetric traveling salesman problem where the arc costs are nonnegative and satisfy the triangle inequality (cf. the preceding exercise).

Estimate the daily heat loss through the wall : Assuming quasi steady conditions for which changes in energy storage within the wall may be neglected, estimate the daily heat loss through the wall if its total surface area is 200 m2.

What do you think about tads expansion plans : How would you describe Sunset Boards' cash flows for 2014? Write a brief discussion. In light of your discussion in the previous question, what do you think about Tad's expansion plans?

A symmetric traveling salesman problem : Traveling Salesman Problem/Triangle Inequality) Consider a symmetric traveling salesman problem where the arc costs are nonnegative and satisfy the following triangle inequality:

Describe the different types of wireless signals : Analyze the maturity of each type of wireless signal and give your opinion on whether or not you believe that type of wireless signal is stable. Is there potential for change and further advancement, or do you suspect there will be limited change?..

User Account

All Pages