MO412 - Mateus de Padua Vicente

Consider the symmetric  Traveling Salesperson Problem (TSP)  on a complete and weighted graph that  satisfies the  triangle inequality .  A student has applied different approaches to find near-optimal tours and has given the following statements: I. The  Closest Neighbor  heuristic always produces a tour whose cost is at most twice the optimum, provided that the graph satisfies the triangle inequality. II. The  Cheapest Insertion  heuristic typically improves over the Closest Neighbor method but does not guarantee any fixed approximation ratio in the general case. III. The  Rosenkrantz–Stearns–Lewis algorithm , based on doubling the minimum spanning tree and shortcutting, guarantees a solution within a factor of 2 of the optimum. IV. The  Christofides algorithm  improves on the MST-doubling approach by adding a minimum-weight perfect matching among the odd-degree vertices of the MST, achieving a 1.5 approximation bound. Which ...

Two undirected networks, Network A and Network B , have identical degree distributions p k p_k ​ but distinct mixing patterns. For each, it is measured the average nearest-neighbor degree function k n n ( k ) k_{nn}(k)  and the degree correlation matrix e j k e_{jk} . So: In Network A , k n n ( k ) k_{nn}(k)  is approximately constant across k k , and e j k e_{jk} ​ roughly factorizes into q j q k q_j q_k ​ . In Network B , k n n ( k ) k_{nn}(k)  decreases systematically with k k , and the e j k e_{jk} ​ matrix shows high values in the upper-left and lower-right corners rather than along the diagonal. Consider the following statements: I. Network A is neutral, while Network B is disassortative. II. Network B is expected to have a negative value of Newman’s correlation coefficient r r . III. If a new Network C were highly assortative, its e j k e_{jk} ​ would concentrate along the diagonal, and k n n ( k ) k_{nn}(k)  would increase with k k . IV. Be...