<p>I think this falls in the category of <a href="https://en.wikipedia.org/wiki/Multi-objective_optimization">multi-objective function</a> optimization problems. </p>

<p>To be specific, it's a <a href="https://en.wikipedia.org/wiki/Multi-objective_optimization#Scalarizing_multi-objective_optimization_problems">linear scalarization</a> of an optimization problem with two objective functions.</p>

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

CC BY-SA 3.0
2015-07-24T19:59:06.040Z
Thanks, this is the terminology for which I was looking. Here is a recent paper about "Structural Complexity of Multiobjective NP Search Problems"
<http://dx.doi.org/10.1007/978-3-642-29344-3_29>.
argentpepper
CC BY-SA 3.0
2015-07-24T11:05:04.313Z
2015-07-24T11:05:04.313Z
Peter Shor 
<p>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?</p>

<p>(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.)</p>

CC BY-SA 3.0
2015-07-24T05:46:31.000Z
I doubt that there is a well-accepted answer in the literature. I would perhaps suggest the name "span".
Gamow
<cc.complexity-theory><optimization>
What do you call the join of two optimization problems?
argentpepper
# What do you call the join of two optimization problems?

(Asked by: username_0 on 2015-07-23)

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.)

**Tags:** cc.complexity-theory, optimization

> **Comments:**
> **username_1**: I doubt that there is a well-accepted answer in the literature. I would perhaps suggest the name "span".  

---

## 1 answers

### Answer by username_2 on 2015-07-24. Score: 6 | Accepted answer

I think this falls in the category of [multi-objective function](https://en.wikipedia.org/wiki/Multi-objective_optimization) optimization problems.

To be specific, it's a [linear scalarization](https://en.wikipedia.org/wiki/Multi-objective_optimization#Scalarizing_multi-objective_optimization_problems) of an optimization problem with two objective functions.

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

> **Comments:**
> **username_0**: Thanks, this is the terminology for which I was looking. Here is a recent paper about "Structural Complexity of Multiobjective NP Search Problems" <http://dx.doi.org/10.1007/978-3-642-29344-3_29>.  

---

