Article ID Journal Published Year Pages File Type
1143251 Operations Research Letters 2011 4 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,