BudgetConstrained DemandWeighted Network Design for Resilient Infrastructure Our work is motivated by an important network design problem in climate adaptation. As floods become more frequent and severe due to climate change, it is increasingly crucial that road infrastructure be strategically upgraded to support postdisaster recovery efforts and normal functionality. We focus on the problem of allocating a fixed budget towards restoring edges to maximize the satisfied travel demand between locations in a network, which we formalize as the budgetconstrained prizecollecting Steiner forest problem. We prove that the satisfiable travel demand objective exhibits restricted supermodularity over forests, and utilize this property to design an iterative algorithm based on maximizing successive modular lower bounds for the objective that finds better solutions than a baseline greedy approach. We also propose an extremely fast heuristic for maximizing modular functions subject to knapsack and graph matroid constraints that can be used as a subroutine in the iterative algorithm, or as a standalone method that matches the greedy baseline in terms of quality but is orders of magnitude faster. We evaluate the algorithms on synthetic data, and apply them to a realworld instance of retrofitting the Senegal national road network against flooding.

Iterative Graph Alignment via Supermodular Approximation Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NPxe2x80x93hard in the worstcase, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this paper, we approach the task of designing an efficient polynomialtime approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorizationmaximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically nondecreasing objective value while always adhering to the combinatorial matching constraints. Experiments on realworld data demonstrate the empirical effectiveness of the algorithm relative to the prevailing stateoftheart.