<p>How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?</p>

<p>It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the MOOP is also NP-Hard.<br>
However, it's not clear to me how to define the worst-case complexity of the MOOP when all of their objective functions can be solved in polynomial-time, separately.</p>

<hr>

<p>There is some different technique for proving that the MOOP is NP-Hard (or its decision version is NP-Complete), or I need to use the same techniques for demonstrating the worst-case complexity of single-objective optimization problems (show that it is in NP, then reduce a NP-Complete problem to my own, ...).</p>

<p>It's hard to find a good discussion regarding this theme on the Internet. Besides, I was unnable to find a good paper or book discussing this issue.</p>

CC BY-SA 4.0
2020-01-04T01:11:23.443Z
Your question as phrased is vague.  There are various ways of dealing with multiple objectives, so the concept of "MOOP" is ambiguous.  And what precisely do you mean by "all of the objective functions can be solved in polynomial-time, separately"?  Can you give a more precise definition of what you mean by a MOOP, and what it means for all of its objectives to be poly-time solvable?  And what you have in mind by somehow solving them all simultaneously?  Or better yet, describe a specific example of what you have in mind.
Neal Young
CC BY-SA 4.0
2020-01-10T13:53:39.533Z
In this paper, https://doi.org/10.1007/978-3-642-46618-2_15 author gives NP-hardness and algorithms for problems like multiobjective shortest path.
Olf
CC BY-SA 4.0
2020-01-31T15:39:24.713Z
And this paper, https://doi.org/10.1007/978-3-319-54157-0_6, challenges most of the claims in the above paper.
FiB
<np-hardness><optimization><time-complexity><np-complete><complexity>
Complexity of multi-objective optimization problems
Iago Carvalho
# Complexity of multi-objective optimization problems

(Asked by: username_0 on 2019-12-31)

How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?

It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the MOOP is also NP-Hard.  
However, it's not clear to me how to define the worst-case complexity of the MOOP when all of their objective functions can be solved in polynomial-time, separately.

---

There is some different technique for proving that the MOOP is NP-Hard (or its decision version is NP-Complete), or I need to use the same techniques for demonstrating the worst-case complexity of single-objective optimization problems (show that it is in NP, then reduce a NP-Complete problem to my own, ...).

It's hard to find a good discussion regarding this theme on the Internet. Besides, I was unnable to find a good paper or book discussing this issue.

**Tags:** np-hardness, optimization, time-complexity, np-complete, complexity
> **Comments:**
> **username_1**: Your question as phrased is vague.  There are various ways of dealing with multiple objectives, so the concept of "MOOP" is ambiguous.  And what precisely do you mean by "all of the objective functions can be solved in polynomial-time, separately"?  Can you give a more precise definition of what you mean by a MOOP, and what it means for all of its objectives to be poly-time solvable?  And what you have in mind by somehow solving them all simultaneously?  Or better yet, describe a specific example of what you have in mind.  
> **username_2**: In this paper, https://doi.org/10.1007/978-3-642-46618-2_15 author gives NP-hardness and algorithms for problems like multiobjective shortest path.  
> **username_3**: And this paper, https://doi.org/10.1007/978-3-319-54157-0_6, challenges most of the claims in the above paper.  

---

## 0 answers

