論文の概要: Connectivity Oracles for Predictable Vertex Failures
- arxiv url: http://arxiv.org/abs/2312.08489v2
- Date: Thu, 15 Feb 2024 17:40:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-16 23:36:50.882423
- Title: Connectivity Oracles for Predictable Vertex Failures
- Title（参考訳）: 予測可能な頂点障害に対するコネクティビティオラクル
- Authors: Bingbing Hu, Evangelos Kosinas, Adam Polak
- Abstract要約: データ構造の前処理時間とクエリ時間は、標準的な複雑な仮定の下で条件的に最適である、と我々は主張する。
我々のデータ構造は、高速な動的サブグラフ接続問題に対して、技術の現状を改善します。
- 参考スコア（独自算出の注目度）: 3.138395828947902
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of designing connectivity oracles supporting vertex failures is
one of the basic data structures problems for undirected graphs. It is already
well understood: previous works [Duan--Pettie STOC'10; Long--Saranurak FOCS'22]
achieve query time linear in the number of failed vertices, and it is
conditionally optimal as long as we require preprocessing time polynomial in
the size of the graph and update time polynomial in the number of failed
vertices.
We revisit this problem in the paradigm of algorithms with predictions: we
ask if the query time can be improved if the set of failed vertices can be
predicted beforehand up to a small number of errors. More specifically, we
design a data structure that, given a graph $G=(V,E)$ and a set of vertices
predicted to fail $\widehat{D} \subseteq V$ of size $d=|\widehat{D}|$,
preprocesses it in time $\tilde{O}(d|E|)$ and then can receive an update given
as the symmetric difference between the predicted and the actual set of failed
vertices $\widehat{D} \triangle D = (\widehat{D} \setminus D) \cup (D \setminus
\widehat{D})$ of size $\eta = |\widehat{D} \triangle D|$, process it in time
$\tilde{O}(\eta^4)$, and after that answer connectivity queries in $G \setminus
D$ in time $O(\eta)$. Viewed from another perspective, our data structure
provides an improvement over the state of the art for the \emph{fully dynamic
subgraph connectivity problem} in the \emph{sensitivity setting}
[Henzinger--Neumann ESA'16].
We argue that the preprocessing time and query time of our data structure are
conditionally optimal under standard fine-grained complexity assumptions.
- Abstract（参考訳）: 頂点障害をサポートする接続オーラクルを設計する問題は、無向グラフの基本的なデータ構造問題の一つである。
先行研究[Duan-Pettie STOC'10; Long-Saranurak FOCS'22] は、失敗した頂点数でクエリ時間線形を達成しており、グラフのサイズで前処理時間多項式、失敗した頂点数で更新時間多項式を必要とする限り条件的に最適である。
我々は、この問題を予測を伴うアルゴリズムのパラダイムで再考する: 失敗する頂点のセットを、少数のエラーまで事前に予測できれば、クエリ時間を改善することができるかどうかを問う。
More specifically, we design a data structure that, given a graph $G=(V,E)$ and a set of vertices predicted to fail $\widehat{D} \subseteq V$ of size $d=|\widehat{D}|$, preprocesses it in time $\tilde{O}(d|E|)$ and then can receive an update given as the symmetric difference between the predicted and the actual set of failed vertices $\widehat{D} \triangle D = (\widehat{D} \setminus D) \cup (D \setminus \widehat{D})$ of size $\eta = |\widehat{D} \triangle D|$, process it in time $\tilde{O}(\eta^4)$, and after that answer connectivity queries in $G \setminus D$ in time $O(\eta)$.
別の観点から見ると、我々のデータ構造は \emph{sensitivity setting} [Henzinger--Neumann ESA'16] における \emph{fully dynamic subgraph connection problem} の技法の状態を改善します。
データ構造の前処理時間とクエリ時間は、標準的なきめ細かい複雑性仮定の下で条件的に最適である。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of
Treelike Topology [0.0]
我々は、与えられたグラフの$G上の一組の$kエージェントの経路を効率的に見つけることに重点を置いており、各エージェントはそのソースからターゲットへの経路を求める。
解の質の重要な尺度は提案されたスケジュールの長さ$ell$、すなわち最長経路の長さである。
MAPFは$G$+$ell$に対してW[1]ハードであり、FPTは$G$+$ell$であることを示す。
論文 参考訳（メタデータ） (2023-12-15T09:42:46Z) - Rule-based Graph Repair using Minimally Restricted Consistency-Improving
Transformations [65.268245109828]
一貫性の維持と一貫性の向上という,一貫性の新たな概念を導入します。
本稿では, 規則に基づくグラフ修復手法を提案する。
論文 参考訳（メタデータ） (2023-07-18T11:20:54Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっている。
グラフ距離と近距離推定のハイブリッドを用いてユークリッド距離を推定する。
本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
論文 参考訳（メタデータ） (2021-07-29T20:37:28Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Minimum projective linearizations of trees in linear time [0.12289361708127873]
我々は、$O(n)$時間で疑いなく実行される射影的および平面的ケースに対して単純なアルゴリズムを導出する。
また、射影に制約のあるルート木の線形配置についても検討する。
論文 参考訳（メタデータ） (2021-02-05T16:35:38Z) - Learning Bayesian Networks Under Sparsity Constraints: A Parameterized
Complexity Analysis [7.99536002595393]
本稿では,ネットワーク上あるいはそのモラル化されたグラフ上に制約を加える際に,最適なベイズネットワークの構造を学習する問題について検討する。
モラル化されたグラフに少なくとも$k$のエッジを持つ最適ネットワークを学習すると、おそらく$f(k)cdot |I|O(1)$-timeアルゴリズムが存在しない。
論文 参考訳（メタデータ） (2020-04-30T12:31:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。