I have two optimization problems, both of whose inputs are from the set $I$ and whose solutions are from the set $S$, one a minimization with objective function $m_{\min}$ and one a maximization with objective function $m_{\max}$. I am studying what I would like to call the "join" or "direct sum" of these two problems, the problem of maximizing $m_{\max}(x, w) - m_{\min}(x, w)$, though I don't know the correct name for such a problem. In my particular case, each problem on its own has a trivial algorithm that produces optimal solutions, but together, the problem is intractable. Has the structural complexity or approximability of optimization problems of this form been studied in a general way?

(The fact that one is a maximization problem and one is a minimization problem is not crucial here, they could both be the same type of optimization.)

  • $\begingroup$ I doubt that there is a well-accepted answer in the literature. I would perhaps suggest the name "span". $\endgroup$
    – Gamow
    Commented Jul 24, 2015 at 5:46

1 Answer 1


I think this falls in the category of multi-objective function optimization problems.

To be specific, it's a linear scalarization of an optimization problem with two objective functions.

I don't know this field very well, but I expect their complexity has been studied.

  • $\begingroup$ Thanks, this is the terminology for which I was looking. Here is a recent paper about "Structural Complexity of Multiobjective NP Search Problems" <dx.doi.org/10.1007/978-3-642-29344-3_29>. $\endgroup$ Commented Jul 24, 2015 at 19:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.