Learning-augmented Assignment: Santa Claus does Load Balancing.

Abstract: 

Assignment problems are among the most well-studied in online algorithms. In these problems, a sequence of items arriving online must be assigned among a set of agents so as to optimize a given objective. This encompasses scheduling problems for minimizing makespan, p-norms, and other objectives, as well as fair division problems such as the Santa Claus problem and Nash welfare maximization. One common feature is that many of these problems are characterized by strong worst-case lower bounds in the online setting. To circumvent these impossibility results, recent research has focused on using additional (learned) information about the problem instance and this has led to dramatic improvements in the competitive ratio over the worst case. In this talk, I will first survey some of this literature (Lattanzi et al., SODA 20; Li and Xian, ICML 21; Banerjee et al., SODA 22; Barman et al., AAAI 22) that addresses specific problems in this domain. I will then proceed to describe recent work with Ilan Cohen that brings these problems under one umbrella: we give a single algorithmic framework  for learning-augmented online assignment for a large class of maximization and minimization objectives.

 

Date: Jun 12, 2024 at 15:00:00 h
Speaker: Debmalya Panigrahi
Affiliation: Duke University, USA
Coordinator: José Verschae
More info at:
Event website
Abstract:
PDF

Posted on Jun 4, 2024 in ACGO, Seminars