Comment by zahlman

Perhaps what is meant is "maximize the difference between the optimal result and the one calculated by the naive greedy algorithm".