2026-08-25T18:47:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27248 2026-08-25T13:18:19Z ddc:004 open_access

One-Exact Approximate Pareto Sets for APX-Hard Multiobjective Problems Bökler, Fritz Chimani, Markus Jasper, Henning multiobjective optimization approximate Pareto sets scalarization There are several frameworks to compute approximate Pareto sets for multiobjective optimization (MOO) problems. An approximate Pareto set that is even precise in one specific objective is called one-exact. In such frameworks, some auxiliary single-objective problem is considered, for which a problem-specific oracle is required. However, often these oracles are required to be a PTAS or even FPTAS. As such, these frameworks are only applicable to "simple" MOO problems that allow for such strong oracles to exist. They are inapplicable whenever the auxiliary problem is APX-hard. We propose a general framework that, for a (possibly even non-constant) accuracy vector β = (β_2, … , β_d) and any ε > 0, computes polynomially sized, one-exact (1,(1 + ε)β_2,… ,(1 + ε)β_d)-Pareto sets for d-objective minimization problems. The framework is analogously applicable to maximization and mixed MOO problems. The running time is polynomial in the time required to solve our auxiliary problem β-RelaxedDualRestrict. Notably, these guarantees hold even if β-RelaxedDualRestrict is APX-hard. We further show that if β-RelaxedDualRestrict cannot be solved in polynomial time, then no (1,β_2, … ,β_d)-Pareto set can be computed in polynomial time. For biobjective problems, our framework even yields a (1,(1 + ε)β_2)-Pareto set of at most 𝒪(log β₂) times the size of the minimum-size one-exact (1,(1 + ε)β_2)-Pareto set. We show that this relative size guarantee is asymptotically tight. Further, we present techniques to obtain suitable oracles for β-RelaxedDualRestrict from existing (single-objective) approximation algorithms, including a general "re-randomization" method that may be of independent interest. Using these, we obtain new best approximation guarantees for several established MOO problems, including Spanner, Clique, TSP, Facility Location, and Set Cover problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fritz Bökler and Markus Chimani and Henning Jasper 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.112 urn:nbn:de:0030-drops-272485 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.112 eng https://creativecommons.org/licenses/by/4.0/legalcode