為替交換問題に対するオンラインアルゴリズムの効率解析

概要

論文の詳細を見る
El-Yanivらは為替交換問題に対して, 単一方向アルゴリズムと双方向アルゴリズムという二種類のオンライン為替交換アルゴリズムを提案している[EFKT92]。単一方向アルゴリズムとは, 所持する通貨(ドル)を別の通貨(円)に交換するものであり, El-Yanivらは提案した単一方向アルゴリズムの競合比が最適であることを証明している。一方双方向アルゴリズムとは, 二つの通貨の間で交換を行なうことで利益を得ることを目的としたアルゴリズムであり, 単一方向アルゴリズムを向きを交互に繰り返し適用することで実現されている。しかしながら競合比の上下限は一致しておらず, この双方向アルゴリズムは最適ではない。また, 我々のこれまでの研究により, 従来より優れた上下限が示されている[DS96]が, これも上下限は一致しておらす, 最適アルゴリズムの設計は未解決である。本稿では, 双方向問題では特定の区間で不利益を受けても, 他の区間で十分な利益を得られればよいという考えに基づき, 前後の区間の相関関係を考慮することで双方向アルゴリズムの改良を行なう。さらに, 従来よりも複雑な入力に対する最適アルゴリズムを示すことで, 下限の改良も行なう。
一般社団法人情報処理学会の論文
1997-09-24

為替交換問題に対するオンラインアルゴリズムの効率解析

スポンサーリンク

概要

著者

関連論文

スポンサーリンク