論文の概要: Minimum-Cost Network Flow with Dual Predictions

• arxiv url: http://arxiv.org/abs/2601.20203v1
• Date: Wed, 28 Jan 2026 03:01:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.744158
• Title: Minimum-Cost Network Flow with Dual Predictions
• Title（参考訳）: 双対予測による最小コストネットワーク流れ
• Authors: Zhiyang Chen, Hailong Yao, Xia Yin,
• Abstract要約: 本稿では,2つの予測を付加した最小コストネットワークフローアルゴリズムを提案する。 本手法は,従来の最小コストフローアルゴリズムである$varepsilon$-relaxationに基づいている。 最小コストフローの2つの応用に関する理論的結果を実証的に検証する。
• 参考スコア（独自算出の注目度）: 4.90881413256913
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Recent work has shown that machine-learned predictions can provably improve the performance of classic algorithms. In this work, we propose the first minimum-cost network flow algorithm augmented with a dual prediction. Our method is based on a classic minimum-cost flow algorithm, namely $\varepsilon$-relaxation. We provide time complexity bounds in terms of the infinity norm prediction error, which is both consistent and robust. We also prove sample complexity bounds for PAC-learning the prediction. We empirically validate our theoretical results on two applications of minimum-cost flow, i.e., traffic networks and chip escape routing, in which we learn a fixed prediction, and a feature-based neural network model to infer the prediction, respectively. Experimental results illustrate $12.74\times$ and $1.64\times$ average speedup on two applications.
• Abstract（参考訳）: 近年の研究では、機械学習による予測が古典的アルゴリズムの性能を向上させることが実証されている。 本研究では,2つの予測を付加した最初の最小コストネットワークフローアルゴリズムを提案する。 提案手法は,古典的な最小コストフローアルゴリズム,すなわち$\varepsilon$-relaxationに基づいている。 我々は無限大ノルム予測誤差の観点から時間複雑性境界を提供するが、これは一貫性と堅牢性の両方である。 また,予測のPAC学習のためのサンプル複雑性境界も証明した。 固定予測を学習する交通ネットワークとチップエスケープルーティングという,最小コストフローの2つの応用に関する理論的結果を実証的に検証し,その予測を推定するための特徴ベースニューラルネットワークモデルについて検討した。 実験結果は、2つのアプリケーションの平均スピードアップに12.74ドルと1.64ドルを表わしている。

関連論文リスト

• Generative Modeling with Continuous Flows: Sample Complexity of Flow Matching [60.37045080890305]
  本稿では,フローマッチングに基づく生成モデルにおいて,サンプルの複雑さを初めて解析する。 速度場推定誤差をニューラルネットワーク近似誤差、有限標本サイズによる統計的誤差、速度場推定のための有限個の最適化ステップによる最適化誤差に分解する。
  論文  参考訳（メタデータ） (2025-12-01T05:14:25Z)
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions [19.537289123577022]
  有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2024-01-02T07:46:33Z)
• Learning-Augmented Maximum Flow [3.0712335337791288]
  本稿では,予測を用いて最大流れ計算を高速化するフレームワークを提案する。 我々は,$m$のエッジフローネットワークと予測フローが与えられた場合,最大フローを$O(meta)$時間で計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-26T14:02:41Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• 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)
• CPNet: Cross-Parallel Network for Efficient Anomaly Detection [20.84973451610082]
  ここでは、性能低下を伴わない計算を最小化するために、効率的な異常検出のためのクロスパラレルネットワーク(CPNet)を提案する。 ネットワーク間シフトモジュールは、シーケンシャルフレーム間の時間的関係をキャプチャして、より正確な将来の予測を可能にする。
  論文  参考訳（メタデータ） (2021-08-10T05:29:37Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

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

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