We deal with the following Chebyshev Path Equipartition problem. Given a node-weighted path with n nodes, and an integer p between 1 and n, one wants to cut p−1 edges so that the weights of the resulting p subpaths (components) are ‘as equal as possible’: by this we mean that the maximum absolute deviation of the component weights from their mean is as small as possible. Aparo and Simeone have given an O(pn2) dynamic programming algorithm. Following a different approach, we propose here a shifting algorithm, which runs ion O(np log p) time. The proof of correctness of the algorithm relies on a nontrivial generalization of the ‘aboveness’ property introduced by Perl and Schach. Under very mild assumptions on the node-weights, an upper bound on the optimal value is established.
