Search NASA⌕ Search
Home/Archive/DOE OSTI

DOE OSTI · 1012379

Evader Interdiction and Collateral Damage

Gutfraind, Alexander
View original source ↗Read source document ↗Export metadata ↓

Abstract

In network interdiction problems, evaders (hostile agents or data packets) are moving through a network towards their targets and we wish to choose sensor placement locations in order to intercept them before they reach their destinations. Sensor locations should be chosen economically, balancing security gains with cost, including the inconvenience sensors inflict upon innocent travelers. We give optimal sensor allocation algorithms for several classes of special graphs and hardness and optimal approximation results for general graphs, including for deterministic or Markov chain-based and oblivious or reactive evaders. In a similar-sounding but much different problem setting posed by [10] where the innocent travelers can also be reactive, we again give optimal algorithms for special cases and hardness and (essentially) optimal approximation results on general graphs.

Explore related subjects

ALGORITHMSAPPROXIMATIONSCOMMUNICATIONSComputer ScienceHARDNESSMathematics & Computing (97)SECURITYSENSORSTARGETS

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Gutfraind, Alexander. 2011-01-01. Evader Interdiction and Collateral Damage. https://www.osti.gov/biblio/1012379

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related reports

DOE OSTI2015

A Framework to Analyze the Performance of Load Balancing Schemes for Ensembles of Stochastic Simulations

Ensembles of simulations are employed to estimate the statistics of possible future states of a system, and are widely used in important applications such as climate change and biological modeling. Ensembles of runs can naturally be executed in parallel. However, when the CPU times of individual simulations vary considerably, a simple strategy of assigning an equal number of tasks per processor can lead to serious work imbalances and low parallel efficiency. This paper presents a new probabilistic framework to analyze the performance of dynamic load balancing algorithms for ensembles of simulations where many tasks are mapped onto each processor, and where the individual compute times vary considerably among tasks. Four load balancing strategies are discussed: most-dividing, all-redistribution, random-polling, and neighbor-redistribution. Simulation results with a stochastic budding yeast cell cycle model are consistent with the theoretical analysis. It is especially significant that there is a provable global decrease in load imbalance for the local rebalancing algorithms due to scalability concerns for the global rebalancing algorithms. The overall simulation time is reduced by up to 25 %, and the total processor idle time by 85 %.

ALGORITHMS↗
DOE OSTI2011

Sequential Construction of Costly Networks

Natural disasters or attacks often disrupt infrastructure networks requiring a costly recovery. This motivates an optimization problem where the objecitve is to construct the nodes of a graph G(V;E), and the cost of each node is dependent on the number of its neighbors previously constructed, or more generally, any properties of the previously-completed subgraph. In this optimization problem the objective is to find a permutation of the nodes which results in the least construction cost. We prove that in the case where the cost of nodes is a convex function in the number of neighbors, the optimal construction sequence is to start at a single node and move outwards. We also introduce algorithms and heuristics for solving various instances of the problem. Those methods can be applied to help reduce the cost of recovering from disasters as well as to plan the deployment of new network infrastructure.

ALGORITHMS↗
DOE OSTI2011

Visualization and Data Analysis at the Exascale

The scope of our working group is scientific visualization and data analysis. Scientific visualization refers to the process of transforming scientific simulation and experimental data into images to facilitate visual understanding. Data analysis refers to the process of transforming data into an information-rich form via mathematical or computational algorithms to promote better understanding. We share scope on data management with the Storage group. Data management refers to the process of tracking, organizing and enhancing the use of scientific data. The purpose of our work is to enable scientific discovery and understanding. Visualization and data analysis has a broad scope as an integral part of scientific simulations and experiments, it is also a distinct separate service for scientific discovery and documentation purposes. Our scope includes an exascale software and hardware infrastructure that effectively supports visualization and data analysis.

ALGORITHMS↗