Skip to main content Skip to footer site map
Mathematics Department

Operations Research and Statistics Seminar

Fall 2022

  • Nov
  • SuiteSparse:GraphBLAS: Graph Algorithms in the Language of Sparse Linear Algebra
    Tim Davis
    Texas A&M University
    Location: CH 110
    Time: 12:00 PM

    View Abstract

    SuiteSparse:GraphBLAS is a full implementation of the GraphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. GraphBLAS provides a powerful and expressive framework for creating graph algorithms based on the elegant mathematics of sparse matrix operations on a semiring. Key features and performance of the SuiteSparse implementation of GraphBLAS package are described. The implementation appears in Linux distros, forms the basis of the RedisGraph module of Redis (a commercial graph database system), appears as C=A*B in MATLAB, and will become the core sparse matrix package in the Julia Language. In terms of performance, graph algorithms written in GraphBLAS can rival or even outperform highly-tuned specialized kernels, while being far simpler for the end user to write.
  • Sep
  • Optimizing Cooperative Interdependent Attack Graphs to Compromise Network Infrastructures
    Joe Alameda
    Location: CH351
    Time: 03:45 PM

    View Abstract

    As infrastructures in our society become increasingly interdependent on one another, the possibility of attacks on these infrastructures utilizing these interdependencies also increases. In this paper, we consider attacks from multiple attackers working fully-cooperatively to reach their goals. Moreover, we model the possibility that more than one exploit may have to be used by an attacker to reach their objective. We provide a mixed-integer program for this attacker model, and we provide an algorithm that gives us an optimal solution. Furthermore, we provide preliminary analysis showing the computational effectiveness of our algorithm when compared to the MIP.
  • Aug
  • Protecting Facilities When the Effect of Protection is Imperfect
    Hugh Medal
    University of Tennessee
    Location: CH351
    Time: 03:45 PM

    View Abstract

    Most system protection optimization models assume that protection actions are perfect in the sense that if a system component is protected it is guaranteed to not fail. In this presentation we study a system protection problem in which protecting a component reduces its likelihood of failure but does not eliminate the chance of failure. In particular, we study a class of facility protection problems in which a defender allocates continuous protection resources to a set of facilities in order to maximize the expected coverage provided by the facilities. The probability that a facility fails depends on the amount of protection resources allocated to it. Exploiting the submodularity of the problem, we first develop a description of the hypograph of continuous submodular functions and then develop a cutting plane algorithm that finds approximate solutions and bounds. Next, we develop a spatial branch-and-bound approach that utilizes the approximate cutting plane algorithm to form an outer approximation and obtain upper bounds for a region. We present computational results that compare our method with a state-of-the-art solver.
go to Top