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?


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.