Skip to content
Preprint

Approximation Algorithms for Multi-Criteria Network Design Problems

Nov 2026 · 0 citations · 36 references
Computer Science

TL;DR

It is shown that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems: Min-max multi-criteria optimization and multi-criteria connectivity augmentation.

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.

View source

Similar papers

Preprint Nov 2026

Multiplicative Weights for Mixed Block Constraints and Maximum Multicommodity Flow

We study multiplicative-weights (MWU) algorithms for block-separable feasibility problems containing both packing and covering constraints. Each iteration optimizes a weighted linear objective over one block, either chosen uniformly at random or visited in a fixed cyclic order. We show that the cyclic algorithm returns...

Vladimir Kolmogorov · 0 citations
Sep 2026

Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization

Experiments on synthetic and real infrastructure networks across graph sizes, budgets, weight distributions, and cost regimes show that, under fixed budgets, distance-proportional costs limit the achievable resistance reduction and shift installed conductance toward shorter links relative to uniform per-unit costs.

Omkar Bhoite, V. S. Dhuli, Stefan Werner et al. · 0 citations
Preprint Nov 2026

Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts

We present a general framework for deterministic constant-round approximation of covering problems in sparse networks in the broadcast CONGEST model, where every vertex broadcasts the same $O(\log n)$-bit message to all its neighbors. The framework combines two independent tools. The first is a solver that computes a $...

S. Amiri, S. Siebertz, W. Wawrzyniak · 1 citation
Preprint Nov 2026

An Improved $(1+2e)$-Approximation Algorithm for Metric Data Placement

We study the metric data placement problem with site-capacity constraints and fixed installation costs, aiming to minimize the total cost of placing data (resources) and accessing their nearest copies. We develop a deterministic polynomial-time approximation algorithm based on a natural linear programming relaxation of...

S. R. Etesami · 0 citations
Preprint Oct 2026

Constrained modularity maximization in complex networks via branch-and-price

Modularity maximization is widely used to identify community structure in complex networks. In many applications, however, community detection must also incorporate prior knowledge and domain-specific requirements beyond network topology. We study constrained modularity maximization with restrictions on the number of c...

Jaewoo Kim, Seung-yeon Lee, Jaemyung Ahn et al. · 0 citations
Preprint Oct 2026

Optimal Online Weighted Connectivity Augmentation

In the online Weighted Connectivity Augmentation Problem (WCAP), we are given a $k$-edge-connected graph on $n$ vertices and a set of additional edges, called links, with nonnegative costs. Pairs of vertices arrive one by one, and an online algorithm must immediately and irrevocably buy links so that each pair becomes...

Mohit Garg, Felix Hommelsheim, Alexander Lindermayr · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.