We study the L∞ path partition problem: given a path of n weighted vertices and an integer k, remove k-1 edges from the path so that the maximum absolute deviation of the weights of the resulting k sub-paths from their mean is minimized. Previously, the best algorithm solves this problem in O(nklogk) time. We present an O(nk) time algorithm. We also give improved solutions for two related problems: the Ld path partition problem and the web proxies placement problem.
