A crash course on spectral graph theory :)

A midshipmen a few years ago concluded "Every math problem can be boiled down to either combinatorics or linear algebra."

Why not both?

Spectral graph theory is the application of linear algebra, in particular eigenvalues, to graphs and networks. This is particularly important because many combinatorial problems are computationally impractical; however, computing eigenvalues, thanks to our newfound understanding of sparse numerical linear algebra, is more efficient. 

In this talk, we will give a crash course of different types of graph-theoretical matrices, the capabilities and limitations of each and some basic results.

The Basics of Sparse Linear Algebra: What is it and Why should we care?

Linear algebra is ubiquitous throughout mathematics, operations research, and computer science. Most matrices encountered in practice are sparse, meaning that the vast majority of entries are zero. Intuitively this seems like it should make the problems easier; however, the presence of sparsity dramatically increases the complexity of standard linear algebra algorithms and software. In this talk, I will give a brief introduction to sparse matrices, a short survey of the applications that we encounter them in, and how accounting for sparsity modifies some of the common algorithms we utilize such as matrix addition, multiplication, and solving systems of equations. I will also discuss some standard pointers to keep in mind when writing code that involves data structures which are sparse. I will wrap up by discussing some of the current trends and research areas in sparse linear algebra.

Basics of Tropical Geometry

Tropical geometry is a branch of algebraic geometry representing the study of geometric properties of polynomials associated with the tropical semiring where classical addition is replaced by the max (or min) function and multiplication is replaced with classical addition. Although a relatively new field, applications of tropical geometry abound in a number scientific fields including biology, game theory, cryptology, causal inference, optimization machine learning, graph theory, and extreme value statistics.  In this introductory lecture we examine basic definitions, notation, arithmetic operations, and tropical analogues of Euclidean geometric structures defined by a tropical, or max(min)-plus, algebra.

Coupled multicommodity flow

Due to applications in commodity transportation, traffic optimization, and project management (just to name a few) the study of network flow is a central topic in operations research and graph theory. Various flow problems are NP-complete and there is a vast literature of research on network flow algorithms. On the other hand, enumeration of nowhere zero flows in a network is "easy" as there is a simple formula with the classic Tutte polynomial. Optimizing and enumerating multicommodity flow is much more complicated. The aim of this talk is to review the single commodity flow enumeration formula using the Tutte polynomial, define a special class of multicommodity flows (coupled) and present a generalization of the classic formula using a generalization of Tutte polynomials. (joint work with Jason Weiss and Gary Lazzaro)

Partitions and statistical distributions

One of the major themes in the theory of partitions is the study of analytic combinatorics, that is, the study of asymptotic or limiting structure of combinatorial functions. In this talk, we will give an overview of how to use analytic techniques to obtain information about "random partitions". In particular, we will give overviews of several methods (some classical, some new) for determining limiting information about the shape and properties of large "random partitions". The talk focuses on two main aspects: constructing "very general" generating functions and "very general" asymptotic growth methods.

Multiobjective Mixed Integer Linear Programming: Easy vs. Hard problems

Many applications for optimization require the consideration of multiple criteria, leading to multicriteria integer programs. Typically, researchers tend to follow one of two naive approaches: First, they abandon the multiple objectives and replace it with one weighted sum of objectives, and call it a day. Second, still using the weighted sum aggregation, they may explore a limited set of weights for each objective, and then consider that sufficient. This introductory seminar will present the aim (and benefits) of seeking the efficient set of solutions (rather than a single/few optimal solutions), with an emphasis on how it offers to improve decision making. We will also see the various types of programs (from linear to integer to mixed integer), and discuss when weighted sum scalarization is and is not sufficient, and when these multicriteria programs start to become interesting versus intractable. Good news comes in two forms: First, many of these classes of problems are already solvable with existing methods (some are even appropriate for MIDN capstone projects)! Second, some of these problems still hold rich research questions.

Continuous approximation for logistics forecasting

In the continuous approximation paradigm we approximate a discrete set of points in Euclidean space as being drawn from a continuous distribution and analyze the objective value of some combinatorial optimization problem as more and more points on which to solve the problem are drawn. We arrive at something like a strong law for your optimization problem. Starting with a routing problem, we will investigate the intuition behind why such results hold and discuss their applications. We will then look at the shape they take for a number of location problems and for a bipartite matching problem with an application to rideshare dispatch. 

Convex Optimization and Trajectory Constraints

Convex optimization and online convex optimization capture a large class of optimization problems, from linear programming to iterative spam filtering. In the first part of this talk, I introduce the standard approaches to solving convex optimization problems and discuss their trade-offs. Standard algorithms, however, can produce sequences of decisions that fluctuate dramatically over time, which can be seen as an instability. One way to address this concern is to enforce a trajectory constraint (e.g., component-wise monotonicity in decisions over time). In the second part of this talk, I will discuss approaches to convex optimization subject to monotonicity constraints.