Like Daniele pointed out, the greedy algorithm assumed in the paper is asymptotically optimal in such a case.