為替交換問題に対する最適に近いオンラインアルゴリズムの設計と解析

概要

論文の詳細を見る
文献[R.El-Yaniv, A.Fiat, R.Karp, and G.Turpin, Proc. of FOCS, (1992).]において, 単一方向交換問題と双方向交換問題という二つの為替交換問題に対するオンラインアルゴリズムが提案されている. 単一方向交換問題とは, 所持する通貨(ドル)を別の通貨(円)に交換するというものであり, 一方向のみの文換を行なう. El-Yaniv らは, 提案した単一方向アルゴリズムが, 競合比という評価方法において最適であることを証明している. 一方, 双方向交換問題とは, ニつの通貨の間で交換を行なうことで利益を得ることを目的としている. EI-Yaniv らはこの問題に対して競合比の上下限を示しているが, その間には大きな差が存在する. 本稿ではこの双方向問題に対する競合比の上下限を改善する. kを円相場関数の極値の数とし, また円相場の変動範囲の上下限の比が2であるならば,従来は(1.278)^kおよび(1.131)^kであった上下限を, 本研究では(1.189)^k and (1.184)^kまで改善している.
一般社団法人情報処理学会の論文
1998-01-22