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.
Abstract
Enhancing the robustness of deployed networks against failures and disruptions is critical for reliable operation. This requires deciding which new links to install and how strongly to weight them under limited resources. We study this problem through the Kirchhoff index, or total effective resistance, a spectral measure of global connectivity. The resulting augmentation problem couples discrete candidate-edge selection with continuous weight allocation under heterogeneous per-unit deployment costs, a total budget, and an exact-cardinality constraint. For a fixed weighted base graph, this yields a mixed-integer formulation and a semidefinite relaxation whose optimum lower-bounds the mixed-integer optimum. We cast the relaxation as a cone program and solve it numerically using a homogeneous self-dual embedding and first-order operator splitting. Feasible discrete designs are recovered through rounding-and-repair procedures and assessed by \emph{a posteriori} gap estimates relative to the numerical semidefinite program (SDP) benchmark. As a scalable alternative, we develop an exact-$k$, budget-feasible greedy heuristic built on rank-one Laplacian updates and biharmonic-distance caching, and interpret its progress through a Bellman value-to-go benchmark with a conservative spectral lower bound on the local policy ratio. 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.
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
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.
This paper introduces the h-hop dominating subnetwork problem (HSDP), a graph-optimization problem that jointly selects a prescribed number of operational vertices, determines the dominant vertices within the selected set, and assigns each selected vertex to a dominant within a given hop range. Unlike classical dominat...
Pablo Adasme, Gustavo Alcántara· Mathematics· 0 citations
A new structural analysis of the Bamas--Drygala--Svensson LP-guided DFS algorithm is given, which combines an exact primal--dual identity for the residual uplink problem with a rank bound that measures fractional support relative to the unit-valued skeleton.
A universal one-sided bound is established that is tight up to constant factors, while constructions across several graph families show that no topology-only converse or universal two-sided scaling law exists.
This work proposes a scalable continuous-optimization algorithm for large-scale single-commodity FCNFP based on an iteratively reweighted least-squares (IRLS) framework and develops an algorithmic variant that incorporates objective-driven perturbation restarts and an anchor-union restricted search that jointly leverag...
Sindura Saraswathi, C. Kümmerle· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.