This paper proposes a scenario-decomposed branch-and-Benders-cut algorithm that solves the finite-scenario SAA model to optimality and establishes distributional equivalence between sampling on the potential graph and then restricting each scenario to the deployed induced network, and sampling directly on the deployed network.
Abstract
This paper studies candidate intermediary node deployment for influence diffusion under the linear threshold model (LTM). Given fixed diffusion sources, target nodes, and a budget, the decision maker selects candidate intermediary nodes to maximize the expected total weight of activated targets. Once deployed, a candidate node enables its associated potential arcs whose other endpoints belong to the effective network. Using the LTM live-arc representation, we establish distributional equivalence between sampling on the potential graph and then restricting each scenario to the deployed induced network, and sampling directly on the deployed network. This leads to a finite-scenario sample-average approximation (SAA) mixed-integer formulation based on canonical live paths; the resulting deployment objective is monotone and supermodular but is generally not submodular, so the classical greedy-approximation guarantee for monotone submodular maximization does not apply in general. Since the compact SAA formulation contains many scenario–target variables and covering constraints, solving the formulation directly can be computationally demanding. We therefore propose a scenario-decomposed branch-and-Benders-cut algorithm that solves the finite-scenario SAA model to optimality. Each scenario subproblem is separable by target and has a closed-form dual optimum, so Benders cuts are separated by scanning required-node sets rather than solving linear programs inside callbacks. On five real networks and 225 SAA instances, the algorithm solves all instances within one hour, averaging 27.46 s; the compact SAA formulation solves 172 instances, with an average capped time of 1444.11 s.
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
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.· arXiv.org· 0 citations
Influence maximization seeks a limited seed set that maximizes diffusion spread. Topology-based rankings are efficient but often ignore finite-horizon dynamics and seed-set redundancy, whereas simulation-assisted greedy methods can be computationally expensive. To balance effectiveness, efficiency, and interpretability...
Tian-Fu Zhang, Bao-Jun Fu· Journal of King Saud Univers...· 0 citations
We introduce the Max-Min Covering Location Blocker Problem, a bilevel optimization problem in which a leader blocks a minimum-cost set of candidate locations so that the optimal coverage of a budget-constrained follower does not exceed a prescribed target. Each customer's coverage is determined by the least favorable o...
Yun-Tian Zhang, Chen Chen, Fabio Furini et al.· 0 citations
An equivalent minimum-cost circulation computation, monotone certificates under parameter uncertainty, and closed-form formulas for bidirected trees, including linear-time evaluation for uniform capacities and an O(|V|log2|V|) centroid decomposition algorithm for heterogeneous capacities are derived.
An MIT and Dana-Farber Institute-led team used large language models to examine nearly 4,000 studies and hundreds of code repositories, revealing gaps in the information needed to scrutinize and reuse published research.