2026-08-10T23:02:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18095 2024-03-06T11:01:00Z ddc:004 open_access

A General Framework for Learning-Augmented Online Allocation Cohen, Ilan Reuven Panigrahi, Debmalya Algorithms with predictions Scheduling algorithms Online algorithms Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimize some objective. This framework captures a broad range of fundamental problems such as the Santa Claus problem (maximizing minimum utility), Nash welfare maximization (maximizing geometric mean of utilities), makespan minimization (minimizing maximum cost), minimization of 𝓁_p-norms, and so on. We focus on divisible items (i.e., fractional allocations) in this paper. Even for divisible items, these problems are characterized by strong super-constant lower bounds in the classical worst-case online model. In this paper, we study online allocations in the learning-augmented setting, i.e., where the algorithm has access to some additional (machine-learned) information about the problem instance. We introduce a general algorithmic framework for learning-augmented online allocation that produces nearly optimal solutions for this broad range of maximization and minimization objectives using only a single learned parameter for every agent. As corollaries of our general framework, we improve prior results of Lattanzi et al. (SODA 2020) and Li and Xian (ICML 2021) for learning-augmented makespan minimization, and obtain the first learning-augmented nearly-optimal algorithms for the other objectives such as Santa Claus, Nash welfare, 𝓁_p-minimization, etc. We also give tight bounds on the resilience of our algorithms to errors in the learned parameters, and study the learnability of these parameters. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ilan Reuven Cohen and Debmalya Panigrahi 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.43 urn:nbn:de:0030-drops-180952 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.43 eng https://creativecommons.org/licenses/by/4.0/legalcode