文献

J-GLOBAL ID：202102285945273551   整理番号：21A0444821

サイクル計数,MAX-CUT,マッチングサイズおよび他の問題に対するマルチパスグラフストリーミング下界【JST・京大機械翻訳】

Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems

著者 (4件)： Assadi Sepehr (Rutgers University,Department of Computer Science,New Brunswick,NJ) ,  Kol Gillat (Princeton University,Department of Computer Science,Princeton,NJ) ,  Saxena Raghuvansh R. (Princeton University,Department of Computer Science,Princeton,NJ) ,  Yu Huacheng (Princeton University,Department of Computer Science,Princeton,NJ)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2020  号： FOCS  ページ： 354-364  発行年： 2020年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ストリーミングモデルにおける次のギャップサイクル計数問題を考慮して,2正則n-頂点グラフGのエッジは,ストリーム中で1対1に到着し,Gは,いくつかの小さなkに対してk-サイクルまたは2k-サイクルの互いに素な結合であると期待した。目標は,限られたメモリを用いてこれらの2つのケースを区別することである。VerbinとYu[SODA2011]はこの問題を導入し,任意の単一パスストリーミングアルゴリズムがn1-Ω(1/k)空間を必要とすることを示した。この結果は,近似MAX-CUT,マッチングサイズ,特性試験,マトリックスランクとSchattenノルム,ストリーミング一意ゲームとCSPs,および多くの他を含む,様々な問題のためのストリーミング下限の証明のために広く使用されたので,Boole Hidden Hyperマッチング通信問題を-haする。その重要性と広い応用範囲にもかかわらず,VerbinとYuの下限技術は,すべての後続結果によって継承される重要な弱点を有する:Boole Hiddenハイパーマッチング問題は,正確に1回の通信があって,実際には,2つのラウンドで対数通信で解決することができる。したがって,この問題に由来するすべてのストリーミング下限は,単一パスアルゴリズムに対してのみ保持されている。この論文の目的は,この状況を修復することである。ギャップサイクル計数問題に対して,k-サイクル対2k-サイクル対-子,k-サイクル対1ハミルトニアンサイクル-要求n{1-1/k{Ω(1/p)|}空間を区別できる,Any p-パスストリーミングアルゴリズムに対する最初のマルチパス下界を証明した。これは,VerbinとYuの研究に対する研究年代測定のこのラインにおける複数の未解決問題の進展を遂げる。この結果と事前低減の単純(または無)修正によって,著者らは,多くの以前の下限をマルチパスアルゴリズムに拡張できる。例えば,筆者らは,(1+ε)がMAX-CUTの値,最大マッチングサイズ,またはn-by-n行列のランクを近似する任意のストリーミングアルゴリズムが,nΩ(1)空間またはΩ(log(1/ε))パスのいずれかを必要とすることを,現在証明できる。これらのすべての問題に対して,事前作業は,2つのパスだけにおいてO(logn)空間アルゴリズムの可能性を開く。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  記憶装置 ,  ゲーム ,  近似法 ,  年代測定 ,  通信 ,  対数 ,  ノルム ,  *ストリーミング
準シソーラス用語： *下界 ,  互いに素 ,  *多経路 ,  ストリーミングアルゴリズム ,  最大マッチング , 【Automatic Indexing@JST】

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

タイトルに関連する用語 (6件)： サイクル ,  計数 ,  Max ,  マッチング ,  サイズ ,  下界