Abstract
We introduce a general online allocation problem that connects several of the most fundamental problems in online optimization. Let M be an npoint metric space. Consider a resource that can be allocated in arbitrary fractions to the points of M. At each time t, a convex monotone cost function c_t: [0,1] → ℝ_+ appears at some point r_t ∈ M. In response, an algorithm may change the allocation of the resource, paying movement cost as determined by the metric and service cost c_t(x_{r_t}), where x_{r_t} is the fraction of the resource at r_t at the end of time t. For example, when the cost functions are c_t(x) = α x, this is equivalent to randomized MTS, and when the cost functions are c_t(x) = ∞⋅1_{x < 1/k}, this is equivalent to fractional kserver.
Because of an inherent scalefreeness property of the problem, existing techniques for MTS and kserver fail to achieve similar guarantees for metric allocation. To handle this, we consider a generalization of the online multiplicative update method where we decouple the rate at which a variable is updated from its value, resulting in interesting new dynamics. We use this to give an O(log n)competitive algorithm for weighted star metrics. We then show how this corresponds to an extension of the online mirror descent framework to a setting where the regularizer is timevarying. Using this perspective, we further refine the guarantees of our algorithm.
We also consider the case of nonconvex cost functions. Using a simple 𝓁₂²regularizer, we give tight bounds of Θ(n) on tree metrics, which imply deterministic and randomized competitive ratios of O(n²) and O(nlog n) respectively on arbitrary metrics.
BibTeX  Entry
@InProceedings{bansal_et_al:LIPIcs.ESA.2022.13,
author = {Bansal, Nikhil and Coester, Christian},
title = {{Online Metric Allocation and TimeVarying Regularization}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {13:113:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16951},
URN = {urn:nbn:de:0030drops169515},
doi = {10.4230/LIPIcs.ESA.2022.13},
annote = {Keywords: Online algorithms, competitive analysis, kserver, metrical task systems, mirror descent, regularization}
}
Keywords: 

Online algorithms, competitive analysis, kserver, metrical task systems, mirror descent, regularization 
Collection: 

30th Annual European Symposium on Algorithms (ESA 2022) 
Issue Date: 

2022 
Date of publication: 

01.09.2022 