2
$\begingroup$

I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has the optimal substructure property. That is, if I have a set U and I construct the A-minimizing tree T out of all the elements in U, each subtree of T must be the A-minimizing tree for the subset of U it corresponds to (same logic goes for the B-minimizing tree).

However, I would like to also construct trees that minimize some positive linear combination of A and B -- let's call this C, such that C = kA + B for a specific k > 0. Does the problem of minimizing C also have optimal substructure? What kind of additional constraints on A, B, and C would I need to impose in order to achieve this?

$\endgroup$

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.