文献

J-GLOBAL ID：202202286444162198   整理番号：22A0917395

並列劣モジュラ関数最小化のためのラウンド数に関する多項式下界【JST・京大機械翻訳】

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization

著者 (3件)： Chakrabarty Deeparnab (Dartmouth College,Hanover,NH) ,  Chen Yu (University of Pennsylvania,Philadelphia,PA) ,  Khanna Sanjeev (University of Pennsylvania,Philadelphia,PA)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 37-48  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： サブモジュール関数(SFM)を最小化する問題は,グラフとマトロイド交差における最小s-tカットを含む,いくつかの基本的組合せ最適化問題の一般的一般化である。Nが宇宙サイズを示すポリ(N)関数評価クエリだけで,サブモジュール関数が最小化できることはよく知られている。しかし,SFMのためのすべての既知の多項式クエリアルゴリズムは,適応性の少なくともNラウンドを必要とする高適応性である。自然質問は,SFMが高度に並列に,すなわち,適応性の多対数ラウンドだけを用いたポリ(N)クエリで効率的に解くことができるかどうかである。SFMを効率的に解決するのに必要な適応度の理解に向けた重要なステップを,ポリ(N)クエリを有するSFMアルゴリズムを示すBalkskiとSingerの非常に最近の研究において採用した。これは,適応性の多対数ラウンドを有する効率的なSFMアルゴリズムの可能性を開く。本研究では,ポリ(N)クエリを生成するサブモジュラ関数最小化のための任意の,おそらくランダム化されたアルゴリズムが,適応性のΩ(N1/3)ラウンドを必要とすることを示すことにより,この可能性を強く除外した。事実,任意の定数|≦0に対して,2{N{1-δ}} queriesクエリーを成すアルゴリズムに対してさえ,適応度数に対する多項式下限を示した。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *多項式 ,  適応性 ,  宇宙空間 ,  対数 ,  マトロイド ,  組合せ最適化問題
準シソーラス用語： *下界 ,  クエリー ,  *劣モジュラ関数 ,  ラウンド数 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (5件)： 劣モジュラ関数 ,  最小化 ,  ラウンド数 ,  多項式 ,  下界