Complexity of min-max subsequence problems |
| |
| Authors: | Wil Michiels Jan Korst |
| |
| Affiliation: | a Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands
b Technische Universiteit Eindhoven, Department of Mathematics and Computing Science, Eindhoven, The Netherlands |
| |
| Abstract: | 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?3. However, the two problems allow a polynomial-time approximation scheme that is linear in n. |
| |
| Keywords: | Computational complexity Polynomial-time approximation scheme Min-max subsequence problem |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
