In the Steiner Path Aggregation Problem , our goal is to aggregate paths in a directed network into a single arborescence without significantly disrupting the paths. In particular, we are given a directed multigraph with colored arcs, a root, and k terminals, each of which has a monochromatic path to the root. Our goal is to find an arborescence in which every terminal has a path to the root, and its path does not switch colors too many times. We give an efficient algorithm that finds such a solution with at most 2 log 4 3 ⁡ k color switches. Up to constant factors this is the best possible universal bound, as there are graphs requiring at least log 2 ⁡ k color switches.

Evacuation planning is an essential part of disaster management where the goal is to relocate people under imminent danger to safety. However, finding jointly optimal evacuation routes and a schedule that minimizes the average evacuation time or evacuation completion time, is a computationally hard problem. As a result, large-scale evacuation routing and scheduling continues to be a challenge. In this paper, we present a game-theoretic approach to tackle this problem. We start by formulating a strategic routing and scheduling game, named the Evacuation Game: Routing and Scheduling (EGRES), where players choose their route and time of departure. We show that: (i) every instance of EGRES has at least one pure strategy Nash equilibrium, and (ii) an optimal outcome in an instance will always be an equilibrium in that instance. We then provide bounds on how bad an equilibrium can be compared to an optimal outcome. Additionally, we present a polynomial-time algorithm, the Sequential Action Algorithm (SAA), for finding equilibria in a given instance under a special condition. We use Virginia Beach City in Virginia, and Harris County in Houston, Texas as study areas and construct two EGRES instances. Our results show that, by utilizing SAA, we can efficiently find equilibria in these instances that have social objective close to the optimal value.

A spanning tree T of graph G is a $\rho$-approximate universal Steiner tree (UST) for root vertex r if, for any subset of vertices S containing r, the cost of the minimal subgraph of T connecting S is within a $\rho$ factor of the minimum cost tree connecting S in G. Busch et al. (FOCS 2012) showed that every graph admits $2^{O(\sqrt{\log n})}$-approximate USTs by showing that USTs are equivalent to strong sparse partition hierarchies (up to poly-logs). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions.We settle these open questions by giving polynomial-time algorithms for computing both $O\left(\log ^{7} n\right)$-approximate USTs and poly-logarithmic strong sparse partition hierarchies. We reduce the existence of these objects to the previously studied cluster aggregation problem and a class of well-separated point sets which we call dangling nets. For graphs with constant doubling dimension or constant pathwidth we obtain improved bounds by deriving $O(\log n)$-approximate USTs and $O(1)$ strong sparse partition hierarchies. Our doubling dimension result is tight up to second order terms.

Vaccines have proven to be extremely effective in preventing the spread of COVID-19 and potentially ending the pandemic. Lack of access caused many people not getting vaccinated early, so states such as Virginia deployed mobile vaccination sites in order to distribute vaccines across the state. Here we study the problem of deciding where these facilities should be placed and moved over time in order to minimize the distance each person needs to travel in order to be vaccinated. Traditional facility location models for this problem fail to incorporate the fact that our facilities are mobile (i.e., they can move over time). To this end, we instead model vaccine distribution as the Dynamic k-Supplier problem and give the first approximation algorithms for this problem. We then run extensive simulations on real world datasets to show the efficacy of our methods. In particular, we find that natural baselines for Dynamic k-Supplier cannot take advantage of the mobility of the facilities, and perform worse than non-mobile k-Supplier algorithms.

Evacuation planning is a crucial part of disaster management. However, joint optimization of its two essential components, routing and scheduling, with objectives such as minimizing average evacuation time or evacuation completion time, is a computationally hard problem. To approach it, we present MIP-LNS, a scalable optimization method that utilizes heuristic search with mathematical optimization and can optimize a variety of objective functions. We also present the method MIP-LNS-SIM, where we combine agent-based simulation with MIP-LNS to estimate delays due to congestion, as well as, find optimized plans considering such delays. We use Harris County in Houston, Texas, as our study area. We show that, within a given time limit, MIP-LNS finds better solutions than existing methods in terms of three different metrics. However, when congestion dependent delay is considered, MIP-LNS-SIM outperforms MIP-LNS in multiple performance metrics. In addition, MIP-LNS-SIM has a significantly lower percent error in estimated evacuation completion time compared to MIP-LNS.

We consider an information dissemination problem where the root node in an undirected graph constantly updates its information. The goal is to keep every other node in the graph as freshly informed about the root as possible. Our synchronous information spreading model uses telephone calls at each time step, in which any node can communicate with at most one neighbor, thus forming a matching over which information is transmitted at each step. We introduce two problems in minimizing two natural objectives (Maximum and Average) of the latency of the root's information at all nodes in the network. After deriving a simple reduction from the maximum rooted latency problem to the well-studied minimum broadcast time problem, we focus on the average rooted latency version. We introduce a natural problem of finding a finite schedule that minimizes the average broadcast time from a root. We show that any average rooted latency scheme induces a solution to this average broadcast problem within a constant factor and conversely, this average broadcast time is within a logarithmic factor of the average rooted latency. Then, we derive a log-squared approximation algorithm for the average broadcast time problem via rounding a time-indexed linear programming relaxation, resulting in a log-cubed approximation for the average latency problem. Surprisingly, we show that using the average broadcast time for average rooted latency introduces a necessary logarithmic factor overhead even in trees. We overcome this hurdle and give a 40-approximation for trees. For this, we design an algorithm to find near-optimal locally-periodic schedules in trees where each vertex receives information from its parent in regular intervals. On the other side, we show how such well-behaved schedules approximate the optimal schedule within a constant factor. * This material is based upon work supported in part by the U. S. Office of Naval Research under award number N00014-21-1-2243 and the Air Force Office of Scientific Research under award number FA9550-20-1-0080.

Evacuation planning is an essential part of disaster management where the goal is to relocate people in a safe and orderly manner. Existing research has shown that such problems are hard to approximate and current methods are difficult to scale to real-life applications. We introduce a notion of fairness and two related objectives while studying evacuation planning, namely: minimizing maximum inconvenience and minimizing average inconvenience. We show that both problems are not just NP-hard to solve exactly, but in fact are NP-hard to approximate. On the positive side, we present a heuristic optimization method MIP-LNS, based on the well-known Large Neighborhood Search framework, that can find good approximate solutions in reasonable amount of time. We also consider a multi-objective problem where the goal is to minimize both objectives and solve it using MIP-LNS. We use real-world road network and population data from Harris County in Houston, Texas (a region that needed large-scale evacuations in the past), and apply MIP-LNS to calculate evacuation plans for the area. We compare the quality of the plans in terms of evacuation efficiency and fairness. We find that the solutions to the multi-objective problem are superior in both of these aspects. We also perform statistical tests to show that the solutions are significantly different.

This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More than half a century ago, Wessel and Bollobás independently solved the problem of minimizing the number of edges in $K_{(s,t)}$-saturated graphs, where $K_{(s,t)}$ is the “ordered” complete bipartite graph with $s$ vertices from the first color class and $t$ from the second. However, the very natural “unordered” analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When $s=t$, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Korándi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in $K_{(s,t)}$-saturated $n$ by $n$ bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for $s=t-1$ with the classification of the extremal graphs. We also improve the estimates of Gan, Korándi, and Sudakov for general $s$ and $t$, and for all sufficiently large $n$.