A Regularization Approach to Metrical Task Systems
Abstract
We address the problem of constructing randomized online algorithms for the Metrical Task Systems (MTS) problem on a metric δ against an oblivious adversary. Restricting our attention to the class of “work-based” algorithms, we provide a framework for designing algorithms that uses the technique of regularization . For the case when δ is a uniform metric, we exhibit two algorithms that arise from this framework, and we prove a bound on the competitive ratio of each. We show that the second of these algorithms is ln n + O (loglog n ) competitive, which is the current state-of-the art for the uniform MTS problem.
Cite
Text
Abernethy et al. "A Regularization Approach to Metrical Task Systems." International Conference on Algorithmic Learning Theory, 2010. doi:10.1007/978-3-642-16108-7_23Markdown
[Abernethy et al. "A Regularization Approach to Metrical Task Systems." International Conference on Algorithmic Learning Theory, 2010.](https://mlanthology.org/alt/2010/abernethy2010alt-regularization/) doi:10.1007/978-3-642-16108-7_23BibTeX
@inproceedings{abernethy2010alt-regularization,
title = {{A Regularization Approach to Metrical Task Systems}},
author = {Abernethy, Jacob D. and Bartlett, Peter L. and Buchbinder, Niv and Stanton, Isabelle},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2010},
pages = {270-284},
doi = {10.1007/978-3-642-16108-7_23},
url = {https://mlanthology.org/alt/2010/abernethy2010alt-regularization/}
}