0
$\begingroup$

I am looking at the following problem. Given an interval I, and a function f over that interval, find sub-intervals for which:

  1. The sum of the length of the sub-intervals is < k;
  2. The sub-intervals are mutually disjoint;
  3. The sum of the integrals over the sub-intervals is maximum.

I think this problem is NP-complete. But I am not sure about it. Any resources about this problem? Thanks.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ It might matter how $f$ is given/represented. $\endgroup$
    – usul
    Jun 1, 2014 at 14:00
  • $\begingroup$ Is the number of subintervals fixed? $\endgroup$
    – fedja
    Jun 2, 2014 at 1:49
  • $\begingroup$ yes, f representation matter. lets simply assume it is continuous function and the number of sub-interval is fixed. actually I think that the problem can be thought as the knapsack problem in sense that we have k sub-intervals each with length and value of sub integral or as cost limited set cover problem in sense we have k subsets each with cost equals its length and want maximize coverage. However, I need to know more about the problem and if there is study about it. $\endgroup$
    – Hani
    Jun 2, 2014 at 7:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.