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. Suppose streaming data needs to be transmitted from the source node to its destination node with the minimum required transmission rate M bits per second. A fraction xi $(0<=$ xi $<=1)$ of line i may be used such that

$$ the transmission rate through line i is xi$$ ri$,$ and a cost ci$$ xiis incurred.

The objective of the problem is to compute xi$,$ for $1<=$ i $<=$ n$,$ such that P$1<=$i$<=$n rixi $>=$ M and P$1<=$i$<=$n cixi is minimized.

Give a greedy algorithm to solve the problem. Justify the optimality of your algorithm

HINT: You can formulate this problem as a slight variation of the Fractional Knapsack

Problem.