ABSTRACT The minimum ‐‐cut problem is one of the most‐studied problems in discrete optimization and has a unique complexity status in multi‐objective optimization. Even though the single‐objective version of the problem can be solved in polynomial time, it has been shown in the seminal work of Papadimitriou and Yannakakis (2000) that there does not exist a multi‐objective fully polynomial‐time approximation scheme (MFPTAS) for the minimum ‐‐cut problem unless . This holds both for the case of objective functions with arc capacities in and for objective functions with general capacities, and even for tractable instances where the number of non‐dominated points is only quadratic in the input size. In this article, we strengthen these results by showing that, assuming , there does not exist an MFPTAS for the minimum ‐‐cut problem with two objectives and arc capacities in , nor for the minimum ‐‐cut problem with two objectives and arc capacities in . This advancement is particularly interesting since the considered problem variants are the only known problems in multi‐objective optimization that do not admit an MFPTAS even though their single‐objective versions are solvable in polynomial time and the problems are tractable , that is, the numbers of non‐dominated points are polynomial (even linear) in the input size. Furthermore, we complement this result by showing that, on graphs of bounded tree‐width, the minimum ‐‐cut problem with polynomially bounded arc capacities can be solved exactly in polynomial time for any constant number of objectives.

Convex approximation sets for multiobjective optimization problems are a well-studied relaxation of the common notion of approximation sets. Instead of approximating each image of a feasible solution by the image of some solution in the approximation set up to a multiplicative factor in each component, a convex approximation set only requires this multiplicative approximation to be achieved by some convex combination of finitely many images of solutions in the set. This makes convex approximation sets efficiently computable for a wide range of multiobjective problems: even for many problems for which (classic) approximations sets are hard to compute. In this article, we propose a polynomial-time algorithm to compute convex approximation sets that builds on an exact or approximate algorithm for the weighted sum scalarization and is therefore applicable to a large variety of multiobjective optimization problems. The provided convex approximation quality is arbitrarily close to the approximation quality of the underlying algorithm for the weighted sum scalarization. In essence, our algorithm can be interpreted as an approximate version of the dual variant of Benson’s outer approximation algorithm. Thus, in contrast to existing convex approximation algorithms from the literature, information on solutions obtained during the approximation process is utilized to significantly reduce both the practical running time and the cardinality of the returned solution sets while still guaranteeing the same worst-case approximation quality. We underpin these advantages by the first comparison of all existing convex approximation algorithms on several instances of the triobjective knapsack problem and the triobjective symmetric metric traveling salesman problem. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This research was supported by the German Research Foundation [Project 398572517]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0220 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0220 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract Scalarization is a common technique to transform a multiobjective optimization problem into a scalar-valued optimization problem. This article deals with the weighted Tchebycheff scalarization applied to multiobjective discrete optimization problems. This scalarization consists of minimizing the weighted maximum distance of the image of a feasible solution to some desirable reference point. By choosing a suitable weight, any Pareto optimal image can be obtained. In this article, we provide a comprehensive theory of this set of eligible weights. In particular, we analyze the polyhedral and combinatorial structure of the set of all weights yielding the same Pareto optimal solution as well as the decomposition of the weight set as a whole. The structural insights are linked to properties of the set of Pareto optimal solutions, thus providing a profound understanding of the weighted Tchebycheff scalarization method and, as a consequence, also of all methods for multiobjective optimization problems using this scalarization as a building block.

Abstract This article investigates the approximation quality achievable for biobjective minimization problems with respect to the Pareto cone by solutions that are (approximately) optimal with respect to larger ordering cones. When simultaneously considering $$\alpha $$ α -approximations for all closed convex ordering cones of a fixed inner angle $$\gamma \in \left[ \frac{\pi }{2}, \pi \right] $$ γ ∈ π 2 , π , an approximation guarantee between $$\alpha $$ α and $$2 \alpha $$ 2 α is achieved, which depends continuously on $$\gamma $$ γ . The analysis is best-possible for any inner angle and it generalizes and unifies the known results that the set of supported solutions is a 2-approximation and that the efficient set itself is a 1-approximation. Moreover, it is shown that, for maximization problems, no approximation guarantee is achievable in general by considering larger ordering cones in the described fashion, which again generalizes a known result about the set of supported solutions.