Answers are grounded in this paper and cite their sources.
Min-max multi-criteria optimization asks for a single feasible solution minimizing the maximum of its costs under 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 -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 )-approximation algorithm. Applying our augmentation procedure iteratively and analyzing its randomized choices jointly across iterations yields an O(log k log )-approximation for the multi-criteria k-edge-connected spanning subgraph (MC-k-ECSS) problem, for every k ≥ 2. We complement these algorithms with a nearly matching lower bound: for every fixed ε > 0, MC-CAP admits no polynomial-time O(log1-ε )-approximation, even when the underlying graph is a star, unless NP(n^logO(1)n). The same hardness extends to the MC-k-ECSS problem.
No takes yet. Share an insight, caveat, or question.
Taziki et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: