A combinatorial metrical task system problem under the uniform metric

Takumi Nakazono; Ken Ichiro Moridomi; Kohei Hatano; Eiji Takimoto

doi:10.1007/978-3-319-46379-7_19

A combinatorial metrical task system problem under the uniform metric

Takumi Nakazono, Ken Ichiro Moridomi, Kohei Hatano, Eiji Takimoto

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings
Editors	Hans Ulrich Simon, Sandra Zilles, Ronald Ortner
Publisher	Springer Verlag
Pages	276-287
Number of pages	12
ISBN (Print)	9783319463780
DOIs	https://doi.org/10.1007/978-3-319-46379-7_19
Publication status	Published - 2016
Event	27th International Conference on Algorithmic Learning Theory, ALT 2016 - Bari, Italy Duration: Oct 19 2016 → Oct 21 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9925 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	27th International Conference on Algorithmic Learning Theory, ALT 2016
Country/Territory	Italy
City	Bari
Period	10/19/16 → 10/21/16

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

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

Cite this

Nakazono, T., Moridomi, K. I., Hatano, K., & Takimoto, E. (2016). A combinatorial metrical task system problem under the uniform metric. In H. U. Simon, S. Zilles, & R. Ortner (Eds.), Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings (pp. 276-287). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9925 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-46379-7_19

A combinatorial metrical task system problem under the uniform metric. / Nakazono, Takumi; Moridomi, Ken Ichiro; Hatano, Kohei et al.
Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings. ed. / Hans Ulrich Simon; Sandra Zilles; Ronald Ortner. Springer Verlag, 2016. p. 276-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9925 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Nakazono, T, Moridomi, KI, Hatano, K & Takimoto, E 2016, A combinatorial metrical task system problem under the uniform metric. in HU Simon, S Zilles & R Ortner (eds), Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9925 LNAI, Springer Verlag, pp. 276-287, 27th International Conference on Algorithmic Learning Theory, ALT 2016, Bari, Italy, 10/19/16. https://doi.org/10.1007/978-3-319-46379-7_19

Nakazono T, Moridomi KI, Hatano K , Takimoto E. A combinatorial metrical task system problem under the uniform metric. In Simon HU, Zilles S, Ortner R, editors, Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings. Springer Verlag. 2016. p. 276-287. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-46379-7_19

Nakazono, Takumi ; Moridomi, Ken Ichiro ; Hatano, Kohei et al. / A combinatorial metrical task system problem under the uniform metric. Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings. editor / Hans Ulrich Simon ; Sandra Zilles ; Ronald Ortner. Springer Verlag, 2016. pp. 276-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{989443d185ae42969502173c68b991d6,

title = "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.",

author = "Takumi Nakazono and Moridomi, {Ken Ichiro} and Kohei Hatano and Eiji Takimoto",

note = "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: {\textcopyright} Springer International Publishing Switzerland 2016.; 27th International Conference on Algorithmic Learning Theory, ALT 2016 ; Conference date: 19-10-2016 Through 21-10-2016",

year = "2016",

doi = "10.1007/978-3-319-46379-7_19",

language = "English",

isbn = "9783319463780",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "276--287",

editor = "Simon, {Hans Ulrich} and Sandra Zilles and Ronald Ortner",

booktitle = "Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings",

address = "Germany",

}

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 -

A combinatorial metrical task system problem under the uniform metric

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this