論文の概要: Incremental Strongly Connected Components with Predictions

• arxiv url: http://arxiv.org/abs/2604.26062v1
• Date: Tue, 28 Apr 2026 18:56:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-30 15:59:36.148307
• Title: Incremental Strongly Connected Components with Predictions
• Title（参考訳）: 予測付きインクリメンタル強結合部品
• Abstract要約: 我々はこのフレームワークを用いて、漸進的に連結されたコンポーネント問題に対する学習データ構造を設計する。 我々のアルゴリズムは、エッジシーケンスの誤予測を受け取り、部分解の事前計算に使用する。 提案アルゴリズムは予測精度が良く,その性能は予測誤差でスムーズに低下することを示す。
• 参考スコア（独自算出の注目度）: 3.761866694781818
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework to design a learned data structure for the incremental strongly connected components (SCC) problem. In this problem, the $n$ vertices of a graph are known a priori and the $m$ directed edges arrive over time. The goal is to efficiently maintain the strongly connected components of the graph after each insert. Our algorithm receives a possibly erroneous prediction of the edge sequence and uses it to precompute partial solutions to support fast inserts. We show that our algorithm achieves nearly optimal bounds with good predictions and its performance smoothly degrades with the prediction error. We also implement our data structure and perform experiments on real datasets. Our empirical results show that the theory is predictive of practical runtime improvements.
• Abstract（参考訳）: 予測付きアルゴリズムは、学習した予測を活用してより高速なアルゴリズムを設計することを目的とした、成長する領域である。 本稿では、このフレームワークを用いて、漸進的強結合コンポーネント(SCC)問題に対する学習データ構造を設計する。 この問題では、グラフの$n$頂点はプリオリとして知られ、時間とともに$m$の有向エッジが現れる。 目的は、挿入後にグラフの強く接続されたコンポーネントを効率的に維持することである。 我々のアルゴリズムは、エッジシーケンスの誤予測を受け取り、高速挿入をサポートする部分解をプリコンプリートするためにそれを利用する。 提案アルゴリズムは予測精度が良く,その性能は予測誤差でスムーズに低下することを示す。 また、データ構造を実装し、実際のデータセットで実験を行います。 実験結果から,本理論は実行時改善の予測可能であることが示された。

関連論文リスト

• Learning-Augmented Streaming Algorithms for Correlation Clustering [6.0943362338120055]
  相関クラスタリングのためのストリーミングアルゴリズムについて検討する。 完全グラフと一般グラフの両方に関する問題に対して,初めて学習強化されたストリーミングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-10-12T17:04:40Z)
• Fast and Accurate Triangle Counting in Graph Streams Using Predictions [4.000869978312742]
  本稿では, グラフストリーム中の三角形の数を予測した最初の効率的かつ実用的なアルゴリズムを提案する。 提案アルゴリズムは,待機室サンプリングと貯水池サンプリングと,エッジの重み,すなわちエッジが関与する三角形の数の予測器を組み合わせる。
  論文  参考訳（メタデータ） (2024-09-23T16:52:11Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。 これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
  論文  参考訳（メタデータ） (2022-10-22T12:58:07Z)
• On Preemption and Learning in Stochastic Scheduling [22.32180964593702]
  本研究では,その時間分布を決定するジョブタイプに属するジョブの単一マシンスケジューリングについて検討する。 我々は,既知型の性能と比較して,サブ線形超過コストを実現するアルゴリズムを設計し,非プリエンプティブの場合の限界を低くする。
  論文  参考訳（メタデータ） (2022-05-31T11:19:32Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。 本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。 実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
  論文  参考訳（メタデータ） (2022-02-22T18:37:23Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Edge Proposal Sets for Link Prediction [39.33358136412426]
  Link Predictionは、将来のエッジを予測したり、グラフに欠けているエッジを推測することを目的としており、推奨システム、実験設計、複雑なシステムに様々な応用がある。 本稿では,前処理ステップとしてエッジセットをグラフに追加するだけで,リンク予測アルゴリズムの性能が向上することを示す。
  論文  参考訳（メタデータ） (2021-06-30T04:59:19Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Learning Output Embeddings in Structured Prediction [73.99064151691597]
  構造化予測に対する強力で柔軟なアプローチは、予測される構造化対象を潜在的に無限次元の特徴空間に埋め込むことである。 原空間における予測は、前像問題の解法により計算される。 本研究では,新しい特徴空間に出力埋め込みと回帰関数の有限近似を共同で学習することを提案する。
  論文  参考訳（メタデータ） (2020-07-29T09:32:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。