Disjoint Segments with Maximum Density.
Journal
Computational Science - ICCS 2005, 5th International Conference, Atlanta, GA, USA, May 22-25, 2005, Proceedings, Part II
Pages
845-850
Date Issued
2005
Author(s)
Chen, Yen Hung
Tang, Chuan Yi
HSUEH-I LU
Abstract
Given a sequence A of numbers and two positive integers ℓ and k, we study the problem to find k disjoint segments of A, each has length at least ℓ, such that their sum of densities is maximized. We give the first known polynomial-time algorithm for the problem: For general k, our algorithm runs in O(nℓk] time. For the special case with k = 2 (respectively, k = 3), we also show how to solve the problem in O(n) (respectively, O(n + ℓ2)} time. © Springer-Verlag Berlin Heidelberg 2005.
Other Subjects
Algorithms; Problem solving; Polynomial approximation; Disjoint segments; Polynomial-time algorithms; Maximum density; Positive integers; Polynomials; Problem solving
Type
conference paper