担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Springer Science and Business Media LLC  

Abstract

The online graph exploration problem, which was proposed by Kalyanasundaram and Pruhs (Theor Comput Sci 130(1):125–138, 1994), is defined as follows: Given an edge-weighted undirected connected graph and a specified vertex (called the origin), the task of an algorithm is to compute a path from the origin to the origin which contains all the vertices of the given graph. The goal of the problem is to find such a path of minimum weight. At each time, an online algorithm knows only the weights of edges each of which consists of visited vertices or vertices adjacent to visited vertices. Fritsch (Inform Process Lett 168:1006096, 2021) showed that the competitive ratio of an online algorithm is at most three for any unicyclic graph. On the other hand, Brandt et al. (Theor Comput Sci 839:176–185, 2020) showed a lower bound of two on the competitive ratio for any unicyclic graph. In this paper, we showed the competitive ratio of an online algorithm is at most 5/2 for any unicyclic graph.

DOI： 10.1007/s10878-024-01192-0

researchmap

その他リンク： https://link.springer.com/article/10.1007/s10878-024-01192-0/fulltext.html

担当区分：筆頭著者,　最終著者   記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Elsevier BV  

DOI： 10.1016/j.tcs.2021.10.005

researchmap

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Elsevier BV  

DOI： 10.1016/j.tcs.2019.10.046

researchmap

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer International Publishing  

DOI： 10.1007/978-3-030-26176-4_29

researchmap

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer International Publishing  

DOI： 10.1007/978-3-319-94776-1_10

researchmap

記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

本稿では, k個のパケットからなるフレーム転送量最大化問題(k-FTM)と呼ばれる,ネットワーク上におけるスイッチのオンラインバッファ管理問題の一問題について考える.本問題は,大きなフレームがk個のパケットに分割されてインターネット上で転送され,受信者はk個全てのパケットを受信できたときに限りフレームを再構成可能という状況をモデル化したものである. Kesselmanらは本問題に対して, k=2の場合でさえ任意のアルゴリズムの競合比は発散することを示した.そこで,入力に制限を加えたk-FTM (k-OFTM)を考え,任意のバッファの大きさB(≧k)に対して,その競合比が高々(2kB)/([B/k])+kとなるアルゴリズムを考案した.また,彼らは2B≧kかつkが2の冪のとき,任意の決定性アルゴリズムの競合比の下限B/([2B/k])=Ω(k)を示した.本稿において,我々はk-OFTMに対する競合比の上限と下限を改良している.主要な結果として,彼らの上界O(k^2)を(5B+[B/k]-4)/([[B/k]/2])=O(k)へ改良し,下界Ω(k)に漸近的に一致させている.また,任意のk≧2と任意のBに対する,決定性アルゴリズムの競合比の下限2k-1と,任意のk≧3と任意のBに対する,確率アルゴリズムの初めての非自明な競合比の下限k-1を与える.

CiNii Research

researchmap

記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

ネットワーク上におけるスイッチのキュー管理は,オンラインバッファ管理問題として定式化されており,多くのモデルが考案されている.我々は,そのモデルの1つである,k(≧2)個のパケットからなるフレーム転送量最大化問題(k-FTM)を扱う.この問題では,データ転送の単位である各フレームをパケットに分割し,転送完了後にフレームを再構成する際の手順に焦点を当てている.各フレームはk個のパケットから構成されており,そのパケットがスイッチ内のFIFOバッファに到着する.1つのフレームを構成するk個のパケットをバッファから転送した場合,そのフレームを再構成することが可能となる.しかし,バッファのサイズは制限されているため,到着したパケットは全てを転送できない場合がある.本問題の目的は,再構成するフレームの数を最大化することである.Kesselmanらは本問題に対して,k=2の場合でさえk-FTMに対する任意のアルゴリズムの競合比は発散することを示している.そこで,入力に制限を加えたk-FTM(k-OFTM)を考え,任意のバッファの大きさB(≧k)に対して,その競合比が高々2kB/⌊B/k⌋+kとなるアルゴリズムを考案し,また,任意のB(≧k)に対して,任意のアルゴリズムの競合比の下限が少なくともB/⌊2B/k⌋であることを示した.我々は,2-OFTMの解析を行い,貧欲なアルゴリズムの競合比が高々3であること,また,任意のアルゴリズムの下限が3であることを示した.

CiNii Research

researchmap

記述言語：英語   出版者・発行元：一般社団法人電子情報通信学会  

オンラインバッファ管理問題は,近年のネットワークにおける主要な論点となっているQoS (Quality of Service)保証実現のための,スイッチのキュー管理をオンライン問題として定式化した問題であり,様々なモデルが考案されている。本論文ではAzarらによって考案されたQoSネットワーク上のマルチキュースイッチを扱ったモデルを取り上げる.Azarらは本モデルの競合比の上限を得るために,"the relaxed model"というモデルを導入している.我々はrelaxed modelに対するオンラインアルゴリズムDSを提案することにより競合比を改良し,その結果としてマルチキュースイッチモデルの競合比の改良を行った.以下は本論文におけるマルチキュースイッチモデルの競合比の改良の一例である.(i)プリエンプション不可能,かつパケットの価値が2値であるモデルにおいて,十分大きなBに対して,決定性アルゴリズムの競合比の上限を4から3.177に改良した.Bは各キューが同時に保持できるパケットの最大数である.(ii)プリエンプション不可能,かつパケットの価値が2値であるモデルにおいて,十分大きなBに対して,乱択アルゴリズムの競合比の上限が高々(17)/2-√<30>&sime;3.023であることを示した.

CiNii Research

researchmap

記述言語：日本語   出版者・発行元：京都大学  

CiNii Research

researchmap

その他リンク： http://hdl.handle.net/2433/58224

記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

オンラインバッファ管理問題は, 近年のネットワーク運用における主要な論点となっているQoS (Quality of Service)保証実現のための, スイッチなどのキュー管理をオンライン問題として定式化した問題であり, 様々なモデルが考案されている.本論文ではその中の1つである共有メモリ型スイッチを扱ったモデルを取り上げる.我々は, アルゴリズムLongest Queue Policy (LQD)の競合比の既知の上限を2-1/Nに改良した.ここで, Nはスイッチの出力ポート数である.

CiNii Research

researchmap