1. The citizens of Antarctica on a future, slightly warmer planet, live in n cities along...

 

Transcribed Image Text:

1. The citizens of Antarctica on a future, slightly warmer planet, live in n cities along the coast of the continent. To get from one city to another they may sail, but the seas are rough and the voyage is slow. They have the idea to lay some roads across the uninhabited interior of the continent. Unfortunately they have not yet invented the traffic light, nor the tunnel nor the bridge, so these roads must be nonintersecting. Multiple roads can, however, leave the same city. (Also, although it doesn't matter much, you may suppose that melting of the glaciers has made the continent essentially round and flat.) The cities are labeled 1,...,n by their position in clockwise order around the coast. For each unordered pair {i, j} the government of Antarctica estimates a certain benefit Bij 0 that will be derived from building a road between cities i,j (1 i,j n). However, the government is somewhat bewildered by its choices, because they wish to compute the set of roads maximizing total benefit; and there are exponentially many feasible sets of roads they could construct. (a) (1 point) Argue rigorously that there are exponentially (in n) many feasible sets of roads. (b) (5 points) Give an O(n)-time algorithm to find the feasible set of roads maximizing total benefit. You may assume the "word model", that is, arithmetic operations on the benefits take unit time. 1. The citizens of Antarctica on a future, slightly warmer planet, live in n cities along the coast of the continent. To get from one city to another they may sail, but the seas are rough and the voyage is slow. They have the idea to lay some roads across the uninhabited interior of the continent. Unfortunately they have not yet invented the traffic light, nor the tunnel nor the bridge, so these roads must be nonintersecting. Multiple roads can, however, leave the same city. (Also, although it doesn't matter much, you may suppose that melting of the glaciers has made the continent essentially round and flat.) The cities are labeled 1,...,n by their position in clockwise order around the coast. For each unordered pair {i, j} the government of Antarctica estimates a certain benefit Bij 0 that will be derived from building a road between cities i,j (1 i,j n). However, the government is somewhat bewildered by its choices, because they wish to compute the set of roads maximizing total benefit; and there are exponentially many feasible sets of roads they could construct. (a) (1 point) Argue rigorously that there are exponentially (in n) many feasible sets of roads. (b) (5 points) Give an O(n)-time algorithm to find the feasible set of roads maximizing total benefit. You may assume the "word model", that is, arithmetic operations on the benefits take unit time.