Zoom: https://illinois.zoom.us/j/85646170025?pwd=WXYrakdybkVObVlSQnhNY0hpQ083Zz09
Abstract:
Minimum cuts are among the most well-studied objects in combinatorial optimization. In this talk, I introduce an elegant but powerful new tool, the minimum isolating cuts, aimed at solving minimum cut problems. I show how this tool leads to a simple yet novel minimum cut algorithm, whose ideas formed the basis of a series of breakthroughs on minimum cut problems.
Next, I claim that minimum isolating cuts is one example of the general, algorithmic method of preconditioning. At a high level, preconditioning systematically reduces input instances of a problem to a smaller class of well-structured instances, which are then solved by a specialized algorithm. I survey my work on preconditioning-based algorithms and, finally, discuss my vision of preconditioning for the future.
Bio:
Jason Li is a Simons Institute postdoctoral fellow working on fundamental graph optimization problems such as minimum cut and maximum flow. His research efforts have led to state-of-the-art algorithms for a wide array of classic problems, including deterministic global minimum cut, minimum k-way cut, Gomory-Hu tree or all-pairs minimum cut, and single-source shortest path in parallel. He has received the EATCS Distinguished Dissertation Award, the Machtey Best Student Paper Award at FOCS 2019, and the Best Paper Award at ESA 2021.
Faculty Host: Chandra Chekuri
Meeting ID: 856 4617 0025; Password: csillinois
