The tramp steamer problem. You are the owner of a steamship that can ply between a group o...

The tramp steamer problem. You are the owner of a steamship that can ply between a group of port cities V. You make money at each port: a visit to city i earns you a profit of pi dollars. Meanwhile, the transportation cost from port i to port j is cij > 0. You want to find a cyclic route in which the ratio of profit to cost is maximized.

To this end, consider a directed graph G = (V, E) whose nodes are ports, and which has edges between each pair of ports. For any cycle C in this graph, the profit-to-cost ratio is

Let r * be the maximum ratio achievable by a simple cycle. One way to determine r* is by binary search: by first guessing some ratio r, and then testing whether it is too large or too small.

Consider any positive r > 0. Give each edge (i, j) a weight of wij = rcij – pj.

(a) Show that if there is a cycle of negative weight, then r

(b) Show that if all cycles in the graph have strictly positive weight, then r > r*.

(c) Give an efficient algorithm that takes as input a desired accuracy e > 0 and returns a simple cycle C for which r (C) ≥ r* −ϵ. Justify the correctness of your algorithm and analyze its running time in terms of |V|, e, and R = max(i, j)∈E (pj/cij).