Consider a resource allocation setting in which n agents have positive and additive utilities over m items. Recall that the algorithm of Lipton et al....

Consider a resource allocation setting in which n agents have positive and additive utilities over m items. Recall that the algorithm of Lipton et al. (2004) takes time O(n3m) to compute an EF1 (envy-free up to one item) allocation. Design an algorithm that takes time O(nm) and computes an EF1 allocation. Prove the running time of the algorithm. Prove that the algorithm always returns an EF1 allocation. Discuss any advantage that the algorithm of Lipton et al. (2004) may have over the new algorithm.