| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142246 | Operations Research Letters | 2015 | 5 Pages |
Abstract
We study a problem on splitting intervals. Let II be a set of nn intervals on a line LL, with non-negative weights. Given any integer k≥1k≥1, we want to find kk points on LL to partition LL into k+1k+1 segments, such that the maximum cost of these segments is minimized, where the cost of each segment ss is the sum of the weights of the intervals in II intersecting ss. We present an O(nlogn)O(nlogn) time algorithm for this problem.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Wei Cao, Jian Li, Shimin Li, Haitao Wang,