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.

  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Jan 4, 2020 at 1:11
  • $\begingroup$ In this paper, doi.org/10.1007/978-3-642-46618-2_15 author gives NP-hardness and algorithms for problems like multiobjective shortest path. $\endgroup$
    – Olf
    Jan 10, 2020 at 13:53
  • $\begingroup$ And this paper, doi.org/10.1007/978-3-319-54157-0_6, challenges most of the claims in the above paper. $\endgroup$
    – FiB
    Jan 31, 2020 at 15:39


Your Answer

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