0
$\begingroup$

This is an attempt to extend an idea from Computer Science.. the dynamic programming based solution of the rod cutting problem (given a rod of an integral length and an array of prices for each integral value of the length, find the optimal cuts that maximize profit). Thinking about it made me wonder.. what if we were not constrained to cut the rod at integral values, but could cut it any where we liked (fractional lengths are possible). Further, lets say that instead of a table of prices corresponding to the integral lengths, we are given a continuous (monotonically increasing, tapering) function that represents the value of the rod at different lengths. For example, for a rod of length 1, the value function might be given by the CDF of a beta distribution. Now, we want to find the number of cuts that we should make and at what values to optimize the total value. Has any one heard of such a problem (I couldn't find any thing online)?

$\endgroup$
  • 2
    $\begingroup$ I think you will need a stronger assumption than monotonicity to be able to solve this. If you assume only that the price function is monotonic then even for one cut into two pieces the sum of the two prices could be close to arbitrary (every reflection-symmetric continuous function, up to addition of a constant, can be decomposed as a sum of a positive monotonic function and its reflection) so there is no way to probe the function and find its optimum. $\endgroup$ – David Eppstein Aug 10 '13 at 18:18
  • $\begingroup$ Okay, lets say the price function is the CDF of the beta distribution with $\alpha = 1$, $\beta = 3$. The red curve in: en.wikipedia.org/wiki/File:Beta_distribution_cdf.svg Or functions that have properties like this one. $\endgroup$ – ryu576 Aug 10 '13 at 18:22
  • $\begingroup$ Also, a heuristic for finding a "good solution" might be to read off the values of the continuous cost function at integral values of the length and solve the dynamic programming problem. If optimality isn't possible, might there be other good heuristics? $\endgroup$ – ryu576 Aug 10 '13 at 18:55

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.