In the paper "An algorithm for optimal partitioning of data on an interval" (link) the authors describe an algorithm for partitioning data on an interval to maximize a fitness function. The fitness function they use is the sum of the fitness of each block in the partition.

My question is, how can this be done if the fitness function were instead the minimum of the fitness of each block? More precisely, how should the algorithm be if the sum in the fitness function in equation (4) was replaced by min?

My guess is that the same algorithm would work, replacing equation (6) with the following:

$$Max_j\,\{min(opt(j-1), end(j,n+1))\}.$$

I would think that this has been done before, but I am unable to find any references. Does anyone have a reference, or agree that my modification is correct?

  • $\begingroup$ Your modification is correct -- the problem keeps the same optimal substructure when $+$ is changed to $\min$. It's a good example of how powerful the DP approach is, and it seems pretty magical if you're new to DP, but I'm a bit surprised that the authors consider this publishable; it's the kind of problem that a professor might ask students to solve themselves after explaining DP and working through a couple of examples on the board. $\endgroup$ – j_random_hacker Oct 13 '19 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.