論文の概要: Connectivity Oracles for Predictable Vertex Failures
- arxiv url: http://arxiv.org/abs/2312.08489v3
- Date: Mon, 1 Jul 2024 13:24:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-02 15:37:58.198269
- Title: Connectivity Oracles for Predictable Vertex Failures
- Title（参考訳）: 予測可能な頂点障害のための接続性オラクル
- Authors: Bingbing Hu, Evangelos Kosinas, Adam Polak,
- Abstract要約: データ構造の前処理時間とクエリ時間は、標準的な複雑な仮定の下で条件的に最適である、と我々は主張する。
我々のデータ構造は、高速な動的サブグラフ接続問題に対して、技術の現状を改善します。
- 参考スコア（独自算出の注目度）: 2.7924160770135007
- 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] は、失敗した頂点数でクエリ時間線形を達成しており、グラフのサイズで前処理時間多項式、失敗した頂点数で更新時間多項式を必要とする限り条件的に最適である。
我々は、この問題を予測を伴うアルゴリズムのパラダイムで再考する: 失敗する頂点のセットを、少数のエラーまで事前に予測できれば、クエリ時間を改善することができるかどうかを問う。
より具体的には、グラフ $G=(V,E)$ と、値が失敗すると予測される頂点のセットが $\widehat{D} \subseteq V$ of size $d=|\widehat{D}|$, preprocesses it in time $\tilde{O}(d|E|)$ を与えられた後、予測値と失敗する頂点の実際のセットとの対称的な差として更新される$\widehat{D} \triangle D = (\widehat{D} \setminus D) \cup (D \setminus \widehat{D})$ of size $\eta = |\widehat{D} \triangle D|$, it in time $\tilde{O}(d|E|)$ が与えられるように、その更新は、D(O)$G(O)$ の接続後に行われる。
別の観点から見ると、我々のデータ構造は、[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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。