On Network Disconnectivities with Applications

Alon Efrat, University of Arizona

September 27, 2016

The lecture will consist of two parts

Near Optimal Resources Allocation for Enhancing Networks Survivability Under Geographically Correlated Attacks

In the work, we present new algorithms for increasing the survivability of WDM networks after geographically correlated attacks. Causes for such attacks might include Electromagnetic Pulse (EMP) attacks, as well as natural disasters, such as solar flares, earthquakes, hurricanes, and floods. The aim is to pre-allocate resources in the network, so their maintenance creates a small overhead on the network functionality. Our algorithm provides a provably almost-optimal solution, with close to linear running time. To obtain this result, we have proven new bounds on the VC-dimensions of topological structures the network might exhibit after the attack.

Joint work with Esther Ezra, Rom Pinchasi, Swaminathan Sankaraman, and Guy Grebla.

Sweeping a Terrain by a Swarm of Collaborative Aerial Vehicles.

In this part we show how to coordinate the motion of a swarm of Unmanned Areal vehicles (UAVs) whose collective task is to sweep a hilly terrain, while seeking an (arbitrarily fast) moving target. We show recent developments in the combinatorial bounds of the underlying structure that their combined visibility regions could form, and derive efficient path planning algorithms.

Joint work with Mikko Nikkilä and Valentin Polishchuk; Micha Sharir; and with Joseph Mitchell, Parrish Myers and Swaminathan Sankararaman.