A Combinatorial Metrical Task System Problem Under the Uniform Metric
Abstract
We consider a variant of the metrical task system (MTS) problem under the uniform metric, where each decision corresponds to some combinatorial object in a fixed set (e.g., the set of all s-t paths of a fixed graph). Typical algorithms such as Marking algorithm are not known to solve this problem efficiently and straightforward implementations takes exponential time for many classes of combinatorial sets. We propose a modification of Marking algorithm, which we call Weighted Marking algorithm. We show that Weighted Marking algorithm still keeps $O(\log n)$ competitive ratio for the standard MTS problem with n states. On the other hand, combining with known sampling techniques for combinatorial sets, Weighted Marking algorithm works efficiently for various classes of combinatorial sets.
Cite
Text
Nakazono et al. "A Combinatorial Metrical Task System Problem Under the Uniform Metric." International Conference on Algorithmic Learning Theory, 2016. doi:10.1007/978-3-319-46379-7_19Markdown
[Nakazono et al. "A Combinatorial Metrical Task System Problem Under the Uniform Metric." International Conference on Algorithmic Learning Theory, 2016.](https://mlanthology.org/alt/2016/nakazono2016alt-combinatorial/) doi:10.1007/978-3-319-46379-7_19BibTeX
@inproceedings{nakazono2016alt-combinatorial,
title = {{A Combinatorial Metrical Task System Problem Under the Uniform Metric}},
author = {Nakazono, Takumi and Moridomi, Ken-ichiro and Hatano, Kohei and Takimoto, Eiji},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2016},
pages = {276-287},
doi = {10.1007/978-3-319-46379-7_19},
url = {https://mlanthology.org/alt/2016/nakazono2016alt-combinatorial/}
}