Euclidian TSP

The Euclidean Traveling Salesman Problem (Euclidean TSP) is a special case of the symmetric TSP where each city corresponds to a point in $\mathbb{R}^d$ and the cost $c_{ij}$ of traveling between cities $i$ and $j$  equals the Euclidean distance between their coordinates.

As the Euclidean distance is symmetric and satisfies the triangle inequality, Euclidean TSP is a special case of Metric TSP, allowing approximation algorithms to be used for a solution.

Consider the Euclidean TSP on 5 cities, located at

A(0, 0)

B(2, 0)

C(2, 1)

D(0, 1)

E(1, 1)


Which of the following statements is true?

a) The optimal tour is achieved by ABCED, costing approximately 5.

b) Any Euclidean TSP can be solved in Polynomial time using the ILP formulation.

c) The Nearest Neighbor heuristic starting from any node always yields a tour of cost 6.

d) The Cheapest Insertion heuristic is better than the Nearest Neighbor for any starting single-node cycle. 

e) None of above


Original Idea: Daniel Gardin


Comments

Post a Comment

Popular posts from this blog

Sierpiński Gasket Graphs

Image
The Sierpiński gasket graphs form one of the most studied examples of self-similar structures in graph theory [1]. They provide a discrete analogue of the classical Sierpiński triangle fractal, preserving both its recursive construction and its combinatorial richness. The sequence begins with the complete graph on three vertices, $S_{1}$, and at each subsequent step, $S_{n+1}$ is obtained from $S_{n}$ by subdividing every triangular face. New vertices are placed at the midpoints of its edges, and these are joined to form a smaller triangle inside. Repeating this process yields a hierarchy of graphs whose geometry captures the recursive pattern of the underlying fractal.   Figure 1. The first 4  Sierpiński gasket graphs. Taken from  Bunimovich et. al (2016) [2] Given this sequence, what is the Global Clustering coefficient of $S_n$, for $n\geq2$ and its limit when $n \to \infty$? $$\textbf{a)}\quad \frac{3^n}{3^{n}-2}, \quad 1$$ $$\textbf{b)}\quad \frac{4\cdot 3^...
Read more

Random Isolated Vertex

Consider a graph consisting of $n$ vertices in which each possible edge is included with probability $p = p(n)$ (a probability that explicitly depends on the size of the graph). This construction provides a probabilistic framework, as described by Gilbert [1], to study typical properties of graphs as $n$ increases. Denote this graph by $G(n, p)$, and consider $p(n) = \frac{1}{\sqrt{n}}$. What is the probability of finding an isolated vertex ( i.e.,  a vertex with no neighbours) in $G(n, p)$ as $n$ increases? Hint: Consider that the probability of finding an isolated vertex in a random graph with $n$ vertices is $P_\mathrm{isolated}(n) = (1-p)^{n-1}$. a) It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{n}$, converging to 1. b)  It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{\sqrt{n}}$, converging to 1. c) It decreases with $n$, approaching $P_\mathrm{isolated}(n) = \frac{\log n}{n}$, converging to 0. d)  It decr...
Read more

Scale-free Networks

The scale-free regime of a network is defined for graphs whose degree distribution is $p(k) \propto k^{-\gamma}$ for $\gamma \in (2, 3)$. Which of the following properties about the resulting networks is true as $\gamma$ approaches $2$ from the right? a) They become indistinguishable from an Erdős–Rényi random network, because their second moment, $\langle k^2 \rangle$, decreases. b)  Vertices with extremely large degrees become more common. c) The expected distance between nodes only increases. d) The tail of $p(k)$ becomes heavy-tailed, indicating a decrease in the average degree, $\langle k \rangle$. e)  None of the above Original idea: Daniel Gardin
Read more