A source node of a data communication network has n communication lines connected to its destination node. Each line i has a transmission rate ri representing the number of bits that can be transmitted per second. A data needs to be transmitted with transmission rate at least M bits per second from the source node to its destination node.

If a fraction xi (0 xi 1) of line i is used (for example, a fraction xi of the full bandwidths of line i is used), the transmission rate through line i becomes xi ri and a cost ci xi is incurred. Assume that the cost function ci (1 i n) is given. The objective of the problem is to compute xi , for 1 i n, such that P 1in rixi M and P 1in cixi is minimized.

(a) Describe an outline of a greedy algorithm to solve the problem.

(b) Prove that your algorithm in part (a) always produces an optimum solution. You should give all the details of your proof.