TY - GEN

T1 - A combinatorial metrical task system problem under the uniform metric

AU - Nakazono, Takumi

AU - Moridomi, Ken Ichiro

AU - Hatano, Kohei

AU - Takimoto, Eiji

N1 - Funding Information:
We thank anonymous reviewers for useful comments. Hatano is grateful to the supports from JSPS KAKENHI Grant Number 16K00305. Takimoto is grateful to the supports from JSPS KAKENHI Grant Number 15H02667. In addition, the authors acknowledge the support from MEXT KAKENHI Grant Number 24106010 (the ELC project).
Publisher Copyright:
© Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84994116122&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84994116122&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-46379-7_19

DO - 10.1007/978-3-319-46379-7_19

M3 - Conference contribution

AN - SCOPUS:84994116122

SN - 9783319463780

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 276

EP - 287

BT - Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings

A2 - Simon, Hans Ulrich

A2 - Zilles, Sandra

A2 - Ortner, Ronald

PB - Springer Verlag

T2 - 27th International Conference on Algorithmic Learning Theory, ALT 2016

Y2 - 19 October 2016 through 21 October 2016

ER -