Aravind Reddy, Northwestern University
Metric labeling is a well-studied generalization of the classic minimum s-t cut problem, which was introduced by Kleinberg and Tardos (JACM 2002). In this talk, we will discuss some recent beyond worst-case analysis results on a popular linear programming formulation of this problem. In particular, we will discuss results on instances which are Perturbation-Resilient. Perturbation-resilience (also known as Bilu-Linial stability) is a popular model for beyond worst-case analysis of approximation algorithms (see book chapter by Makarychev and Makarychev for an introduction). This talk will be based on a series of works by me and my collaborators (Hunter Lang, Aravindan Vijayaraghavan, and David Sontag) which appeared in AISTATS 2018, 2019, and 2021.
Join via Zoom