抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
著者らは,Becchetti,Clementi,Natale,PasqualおよびPosta(2019)によって導入された反復ボールイントビンプロセスを研究した。この過程はnビンに任意に分布するmボールから始まる。各ラウンドt=1,2.で,1つのボールを各非空ビンから選択し,次にそれを独立に,そしてランダムで一様に選択したビンに配置した。以下の結果を証明した。任意のn≦m≦poly(n)に対して,最大負荷に対するΩ(m/n.logn)の下限を証明した。特別なケースm=nに対して,これは[BCNPP19]で示されたように,O(logn)の上限と一致する。また,それは,m=nに対して最大負荷が少なくとも多項式に大きい時間間隔でω(logn/loglogn)である[BCNPP19]の予想に正の回答を与える。m→∞[ω(n),nlogn]に対して,この新しい下限は,最大負荷がO(logn)を維持する[BCNPP19]の予想を改善する。任意のn≦m≦poly(n)に対して,多項式大時間間隔の全ステップに対して最大負荷に対するO(m/n.logn)の上限を証明した。これは,乗法定数までの下限と合致する。.また,任意のm≧nに対して,著者らの解析は,最悪ケース初期分布に対してさえ,O(m ̄2/n)最大負荷を有する構成に達するO(m ̄2/n)待ち時間を意味する。.任意のm≧nに対して,あらゆるボールがO(mlogm)ラウンドであらゆるビンを訪れることを示した。m=nに対して,これは[BCNPP19]におけるO(nlog ̄2n)の以前の上限を改善する。また,上限が任意のn≦m≦poly(n)に対して乗法定数まで強まることを証明した。【JST・京大機械翻訳】