@inproceedings{ce4e63a241f24b7e941915685eb123f7,
title = "The Average-Value Allocation Problem",
abstract = "We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to approximate beyond a factor of e−e1, and provide a e4−e1-approximate offline algorithm. For the online setting, we show that no non-trivial approximations are achievable under adversarial arrivals. Under i.i.d. arrivals, we present a polytime online algorithm that provides a constant approximation of the optimal (computationally-unbounded) online algorithm. In contrast, we show that no constant approximation of the ex-post optimum is achievable by an online algorithm.",
keywords = "approximation algorithm, online algorithm, Resource allocation, return-on-spend constraint",
author = "Kshipra Bhawalkar and Zhe Feng and Anupam Gupta and Aranyak Mehta and David Wajc and Di Wang",
note = "Publisher Copyright: {\textcopyright} Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc, and Di Wang.; 27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024 ; Conference date: 28-08-2024 Through 30-08-2024",
year = "2024",
month = sep,
doi = "10.4230/LIPIcs.APPROX/RANDOM.2024.13",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Amit Kumar and Noga Ron-Zewi",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024",
}