Georgia Institute of Technology College of Sciences

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics, convex geometry, fair allocations, combinatorics, spectral graph theory, network design, and random processes. In an instance of a determinant maximization problem, we are given a collection of vectors $U = {v_1, \ldots, v_n}$ in $d$ dimensions, and a goal is to pick a subset $S$ of given vectors to maximize the determinant of the matrix $\sum_{i \in S} v_i v_i^T$. Often, the set $S$ of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint ($|S| \leq k$) or matroid constraint ($S$ is a basis of a matroid defined on the vectors). In this talk, we give a polynomial-time deterministic algorithm that returns an $r^{O(r)}$-approximation for any matroid of rank $r \leq d$. Our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improves any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the determinant function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

This talk is based on joint work with Adam Brown, Madhusudhan Pittu, Mohit Singh, and Prasad Tetali.

While gerrymandering has been widely suspected in Georgia for years, it has been difficult to quantify. We generate a large ensemble of randomly generated non-partisan maps that are sampled from a probability distribution which respects the geographical constraints of the redistricting process. Using a Markov chain Monte Carlo process and techniques involving spanning trees, we can quickly generate a robust set of plans.

Based on historical voting data, we compare the Georgia congressional redistricting plan enacted in 2021 with the non-partisan maps. We find that the 2021 plan will likely be highly non-responsive to changing opinions of the electorate, unlike the plans in the ensemble. Using additional spatial analysis, we highlight areas where the map has been redrawn to weaken the influence of Democratic voters.

This talk is based on joint work with Swati Gupta, Gregory Herschlag, Jonathan Mattingly, Dana Randall, and Zhanzhan Zhao.

The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no inclusion-maximal clique is monochromatic (ignoring isolated vertices). 

For the binomial random graph G_{n,p} the clique chromatic number has been studied in a number of works since 2016, but for sparse edge-probabilities in the range n^{-2/5} \ll p \ll 1 even the order of magnitude remained a technical challenge.

Resolving open problems of Alon and Krivelevich as well as Lichev, Mitsche and Warnke, we determine the clique chromatic number of the binomial random graph G_{n,p} in most of the missing regime: we show that it is of order (\log n)/p for edge-probabilities n^{-2/5+\eps} \ll p \ll n^{-1/3} and n^{-1/3+\eps} \ll p \ll 1, for any constant \eps > 0.

Perhaps surprisingly for a result about random graphs, a key ingredient in the proof is an application of the probabilistic method (that hinges on careful counting and density arguments).

This talk is based on joint work with Lutz Warnke.

Parallel server systems have received a lot of attention since their introduction about 20 years ago. They are commonly used to model a situation where different type of jobs can be treated by servers with different specialties like data and call centers. Exact optimal policies are often not tractable for those systems. Instead, part of the literature was focused on finding policies that are asymptotically optimal as the load of the network approaches a value critical for stability (heavy traffic approximations). This is done by obtaining a weak convergence to a brownian control problem that is linked to a non-linear differential equation (Hamilton-Jacobi-Bellman). Asymptotically optimal policies have been analyzed for a long time under a restrictive assumption that is not natural for practical applications. This talk will present recent developments that allow for a more general asymptotic optimality result by focusing on the simplest non-trivial example.