Abstract

Online resource allocation problem is a central problem in many areas of Computer Science, Operations Research, Economics, and Networks. In this problem, requests arrive sequentially, and each request can be satisfied in multiple ways, each consuming a certain amount of resources while generating different values. The objective is to maximize the overall value without exceeding the budget for any resource. Of particular interest in this problem is the design of pricing algorithms that present each incoming request with prices for the resources, enabling the request to make a value-maximizing decision based on current resource prices. The goal is to achieve a (1+ϵ)-approximation to the hindsight optimum, where ϵ>0 is a small constant.

Prior works have established that (1+ϵ)-approximation pricing algorithms exist for i.i.d. requests, provided that each resource has a large budget. Our goal is to obtain similar guarantees for non-identical request distributions or when the requests have outliers that do not satisfy the stochastic assumptions. Our main contribution is in resolving both these questions via a simple exponential pricing algorithm: it gives a (1+ϵ)-approximation for online resource allocation with large budgets, requires only O(poly(1/ϵ)) samples from the  non-identical distributions, and can robustly handle outliers/augmentations.

Time

2024-04-29  15:30 - 16:30   

Speaker

Yifan Wang, Georgia Institute of Technology

Room

Room 308