Improved algorithms for path partition and related problems

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

► We study the LL infinity path partition problem.
► We show that the matrix in the DP is totally monotone.
► We study the LdLd path partition and the web proxies placement problems.
► We model them as the kk-link shortest path problem with Monge property.