Academic Paper

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

April, 2022

Abstract

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m1+o(1) time. Our algorithm builds the flow through a sequence of m1+o(1) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized mo(1) time using a new dynamic graph data structure.

A Final Report Card on the States’ Response to COVID-19

April, 2022

Abstract

Almost exactly two years ago COVID-19 spread to the United States. Following the federalism model, the 50 states and their governors and legislators made many of their own pandemic policy choices to mitigate the damage from the virus. States learned from one another over time about what policies worked most and least effectively in terms of containing the virus while minimizing the negative effects of lockdown strategies on businesses and children.

Pages