抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
多くの組合せ最適化問題は,ネットワーク分解[Ghaffari,Kuhn,Maus,STOC2018]によるLOCALモデルのポリ(logn,1/ε)ラウンドの(1±ε)因子内で近似できる。これらの手法は,非制限サイズのメッセージ送信を必要とし,従って,それらはCONGESTモデルに拡張せず,メッセージサイズをO(logn)ビットに制限する。本論文では,CONGESTモデルにおける固定小数を除くグラフにおいて,最大加重マッチング,最大独立集合および相関クラスタリングを含む,多くの組合せ最適化問題に対するポリ(logn,1/ε)ラウンド(1±ε)近似アルゴリズムを得るための一般的フレームワークを開発した。このクラスのグラフは,平面グラフ,有界ゲニスグラフ,および有界ツリー幅グラフを含む,文献で研究された多くのスパースネットワーククラスをカバーする。さらに,著者らのフレームワークは,互いに素な結合の下で閉じられる任意のマイナーな閉グラフ特性のための効率的な分散特性試験アルゴリズムを与えるのに適用でき,[Lev,Medina,およびRon,PODC2018&Distributed Computing 2021]における平面性のための以前の分散特性試験アルゴリズムを著しく一般化する。。”そのフレームワークは,”Levi,Medina,およびRon,PODC 2018&Distributed Computing 2021]における平面性のための以前の分散特性試験アルゴリズムを著しく一般化する。このフレームワークは,分散膨張機分解アルゴリズム[ChangとSaranurak,FOCS2020]を用いて,グラフを高コンダクタンスのクラスタに分解する。固定マイナーな小さなエッジ分離器を除く任意のグラフを示した。この結果を用いて,拡張器分解における各クラスタにおける高度頂点の存在を示し,クラスタの全グラフトポロジーを頂点に経路付けできる。LOCALモデルにおけるネットワーク分解の使用と同様に,頂点はクラスタにより誘起された部分グラフ上で任意の局所計算を行うことができ,クラスタ上の結果を放送する。【JST・京大機械翻訳】
