| 作成者 |
|
|
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
| 発行日 |
|
| 会議情報 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
| 関連DOI |
|
| 関連情報 |
|
| 概要 |
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(logn) 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.続きを見る
|
Mendeley出力
