Complexity of min-max subsequence problems
We determine the computational complexity of the problem of ordering a set of n numbers, either into a sequence or a cycle, such that the maximum sum of any k successive numbers is minimal. Both problems are easy for k = 2 and strongly NP-hard for any k greater than or equal to 3. However, the two problems allow a polynomial-time approximation scheme that is linear in n. (C) 2003 Elsevier B.V. All rights reserved.
min-max subsequence problem computational complexity polynomial-time approximation scheme