1. Prove that making a shortcut of the kind used by the twice-around-the-tree algorithm cannot increase the tour's length in a Euclidean graph.
2. What is the time efficiency class of the greedy algorithm for the knapsack problem?
3. Prove that the performance ratio RA of the enhanced greedy algorithm for the knapsack problem is equal to 2.