Approximation Guarantees for Data-Driven Algorithm Design (in person only)

Data-Driven Algorithm Design refers to the idea of using typical problem-instances from a domain of interest to help produce an algorithm that performs particularly well on that domain.  This idea has a long history in AI, and recently there have been exciting theoretical advances developing methods for proving guarantees for this approach (see, e.g., [Balcan 2020, Balcan et al. 2024]).   In this talk, I will discuss work on using ideas from approximation algorithms and competitive analysis to simplify the algorithmic challenge involved, and perhaps also make it easier to compare to stronger benchmarks, by willingly giving up some constant (or logarithmic or polynomial) factors. I will focus on the setting of algorithms that can benefit from “warm start” initialization, where we will also see connections to several classic algorithmic problems.