- Combinatorial
Scientific Computing: I am broadly interested in
combinatorial optimization and development of parallel
combinatorial (graph) algorithms for matching, coloring,
clustering, extraction of chordal subgraphs, and network flow.
- Study of electric
power grids : I am broadly interested in the research
of combinatorial algorithms with applications to the study of
electric power grids.
- Cyber security
: Graph-theoretic approaches play a key role in cyber security. In
this context, my research interests are in developing
graph-theoretic methods for modeling and metrics, and applications
in cyber system resilience.
Projects/Funding
- Department of
Energy-Advanced Scientific Computing Research (DOE-ASCR):
Multifaceted Mathematics for Complex Energy Systems (M2ACS). 2012
- 2017.
- Department
of Energy-Advanced Scientific Computing Research
(DOE-ASCR): Integrated End-to-End Performance Prediction
and Diagnosis for Extreme Scientific Workflows (IPPD).
2015 - 2018.
- Department of Defense:
Center for Adaptive Supercomputing Software-Multithreaded
(CASS-MT). 2009 - 2015.
Laboratory Directed Research
and Development, Pacific Northwest National Laboratory
(PI/Co-PI/Senior Personnel):
- Rendezvous: Optimization and
Stochastic Algorithms for Asymmetric Resilient Infrastructure. 2015
- 2016.
- Resilience in Large-Scale
Distributed Control Systems. 2015 - 2016.
- Theory of Resilience:
Algorithms for Resilient decision making towards Reconstitution of
cyber-infrastructure. 2013 - 2016.
- M&Ms4Graphs: A
Multi-scale, Multi-Dimensional Graph Analytics Framework for Cyber
Security. 2013 - 2016.
- Shyre: Streaming Hypothesis
Reasoning. 2014 - 2015.
- Future Power Grid Control
Paradigm. 2012 - 2015.
- Linear Algebra Solvers and
Associated Matrix-Vector Kernels for Power Grid Simulations. 2010
- 2015.
- Comparing Performance on
Different High Performance Computing Architectures. 2010.
Synergistic Activities
- Co-organized the Workshop on
Parallel Algorithms and Software for Analysis of Massive Graphs
(ParGraph), held in conjunction with HiPC, India, 2011 and 2012.
- Co-organized mini-symposiums
at SIAM conferences (Annual Meeting, Parallel Processing for
Scientific Computing, Computational Science and Engineering).
- Participated on the program
committees for several conferences and workshops.
Doctoral Thesis
Abstract: A
matching M in a graph is a subset of edges such that no
two edges in M are incident on the same vertex. Matching
is a fundamental combinatorial problem with many applications. In
the first part of this thesis, we develop exact and approximation
algorithms for vertex weighted matchings, an under-studied variant
of the weighted matching problem. We propose three exact algorithms,
three half approximation algorithms, and a two-third approximation
algorithm. We exploit inherent properties of this problem such as
lexicographical orders, decomposition into sub-problems, and the
reachability property, not only to design efficient algorithms, but
also to provide simple proofs of correctness of the proposed
algorithms. In the second part of this thesis, we describe work on a
new parallel half-approximation algorithm for weighted matching.
Algorithms for computing optimal matchings are not amenable to
parallelism, and hence we consider approximation algorithms here. We
extend the existing work on a parallel half approximation algorithm
for weighted matching and provide an analysis of its time
complexity. We support the theoretical observations with
experimental results obtained with MatchBoxP, toolkit designed and
implemented in C++ and MPI using modern software engineering
techniques. The work in this thesis has resulted in better
understanding of matching theory, a functional public-domain
software toolkit, and modeling of the sparsest basis problem as a
vertex-weighted matching problem.