Approximation Algorithms for Multi-Criteria Network Design Problems

Abstract

Min-max multi-criteria optimization asks for a single feasible solution minimizing the maximum of its costs under $\ell$ nonnegative cost functions, a formulation that captures both fairness across groups and robustness across scenarios. It has proved hard to approximate even for basic problems: for robust shortest paths, polylogarithmic approximations are known only in quasi-polynomial time. For network design, the best known guarantee is an $\ell$-approximation, which is tight for the natural LP relaxation. We show that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems. For multi-criteria connectivity augmentation (MC-CAP), which asks to increase the edge connectivity of a given undirected graph by one, we give a randomized polynomial-time $O(\log \ell)$-approximation algorithm. Applying our augmentation procedure iteratively and analyzing its randomized choices jointly across iterations yields an $O(\log k \log \ell)$-approximation for the multi-criteria $k$-edge-connected spanning subgraph (MC-$k$-ECSS) problem, for every $k \geq 2$. We complement these algorithms with a nearly matching lower bound: for every fixed $\varepsilon > 0$, MC-CAP admits no polynomial-time $O(\log^{1-\varepsilon} \ell)$-approximation, even when the underlying graph is a star, unless $\mathsf{NP}\subseteq\mathsf{DTIME}\bigl(n^{\log^{O(1)}n}\bigr)$. The same hardness extends to the MC-$k$-ECSS problem.