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.

Given an undirected graph G with edge weights and lengths, a minimum α-spanner is a least-weight subgraph H ⊆ G that preserves distances w.r.t. the lengths between all node pairs up to a factor of α. Literature often takes the simplifying assumption of a single (coupled) edge function for weights and lengths. For such instances, several exact and non-exact algorithms are known and have been thoroughly evaluated in practice. However, many practical instances have decoupled form, as their weights and lengths are generally independent. Due to the increased complexity, only few (and even fewer practical) algorithms are able to guarantee low-weight solutions. This prompts practitioners to force their naturally decoupled instances into a coupled format, forsaking any quality guarantee. We implement several exact, approximative and heuristic algorithms for decoupled α-spanners, and use algorithm engineering to speed them up in practice. Our hypothesis-driven experiments evaluate their performance w.r.t. solution quality and speed. Generally, many practical instances can indeed be solved exactly within reasonable time, while LP-based approximation algorithms are not worthwhile. We find that standard greedy algorithms often yield acceptable results, but there are also practical instances for which they yield arbitrarily poor solutions. Here, augmented greedy variations offer a good compromise between solution quality and speed.

Collaboration among drone swarms in various applications often requires dynamic data exchange to optimize their missions. When employing device-to-device (D2D) communications, drones must form connected topologies enabling multi-hop communication. Maintaining a connected topology during their movement to new locations is a major challenge that has not been tackled in the literature. In this paper, we first formalize this problem, proving the decision version is NP-Hard, and break it into sub-problems, detailing their complexity under certain constraints. We then propose polynomial time solutions to these subproblems. Our proposed approach first makes a location assignment for each drone to determine where to move as their next locations. Next, our approach relocates each drone to their designated target location without losing in-network connectivity of the drone topology. We achieve this by leveraging a two-step approach: contraction and re-expansion. In the contraction phase, drones converge towards a specific location, reducing network diameter and increasing connectivity. In the expansion phase, drones disperse to their new target positions. Mathematical proofs and extensive simulations validate our method’s effectiveness in maintaining connectivity during drone relocations.

Given a weighted graph $G$, a minimum weight $α$-spanner is a least-weight subgraph $H\subseteq G$ that preserves minimum distances between all node pairs up to a factor of $α$. There are many results on heuristics and approximation algorithms, including a recent investigation of their practical performance [20]. Exact approaches, in contrast, have long been denounced as impractical: The first exact ILP (integer linear program) method [48] from 2004 is based on a model with exponentially many path variables, solved via column generation. A second approach [2], modeling via arc-based multicommodity flow, was presented in 2019. In both cases, only graphs with 40-100 nodes were reported to be solvable. In this paper, we briefly report on a theoretical comparison between these two models from a polyhedral point of view, and then concentrate on improvements and engineering aspects. We evaluate their performance in a large-scale empirical study. We report that our tuned column generation approach, based on multicriteria shortest path computations, is able to solve instances with over 16000 nodes within 13 minutes. Furthermore, now knowing optimal solutions for larger graphs, we are able to investigate the quality of the strongest known heuristic on reasonably sized instances for the first time.

We consider the multiobjective shortest path (MOSP) problem. While known approximation algorithms allow a polynomial running time, the degrees of these polynomials are dependent on the number of objective functions. Unfortunately, this also holds true for their best-case. Exact algorithms, while attaining an exponential worst-case running time even in the number of nodes, allow for far better best-case performance and are thus preferred in practice. We introduce a new general approximation framework for MOSP. It aims at combining strong worst-case guarantees with practically useful performance. It allows for various labeling strategies as employed by exact algorithms; thus, decades of research can be utilized. We conduct a comprehensive computational study to compare our framework to known approximations and exact algorithms. For many, this is their first practical investigation. Furthermore, this is the first time that graphs of practically relevant sizes as well as real-world instances are considered in the context of MOSP approximation. The results show that our framework is superior to the known approximation methods in running time and quality. They also demonstrate the usefulness and limits of approximations compared to exact methods.