論文の概要: Improved Approximations for Hard Graph Problems using Predictions
- arxiv url: http://arxiv.org/abs/2505.23967v1
- Date: Thu, 29 May 2025 19:47:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-02 19:47:52.644536
- Title: Improved Approximations for Hard Graph Problems using Predictions
- Title（参考訳）: 予測を用いたハードグラフ問題の近似の改善
- Authors: Anders Aamand, Justin Y. Chen, Siddharth Gollapudi, Sandeep Silwal, Hao Wu,
- Abstract要約: 我々は予測を組み込んだNPハードグラフ問題に対する近似アルゴリズムを改良した。
我々の予測モデルは、Cohen-Addad, d'Orsi, Gupta, Lee, Panigrahiによる$varepsilon$-predictionフレームワークの上に構築され、拡張されます。
- 参考スコア（独自算出の注目度）: 13.827632579682795
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the $\varepsilon$-prediction framework by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi (NeurIPS 2024). We consider an edge-based version of this model, where each edge provides two bits of information, corresponding to predictions about whether each of its endpoints belong to an optimal solution. Even with weak predictions where each bit is only $\varepsilon$-correlated with the true solution, this information allows us to break approximation barriers in the standard setting. We develop algorithms with improved approximation ratios for MaxCut, Vertex Cover, Set Cover, and Maximum Independent Set problems (among others). Across these problems, our algorithms share a unifying theme, where we separately satisfy constraints related to high degree vertices (using predictions) and low-degree vertices (without using predictions) and carefully combine the answers.
- Abstract（参考訳）: 本研究では,過去のデータから学習した予測を組み込むことにより,NP-hardグラフ問題に対する近似アルゴリズムを改良した。
我々の予測モデルは、Cohen-Addad, d'Orsi, Gupta, Lee, Panigrahi (NeurIPS 2024)による$\varepsilon$-predictionフレームワークの上に構築され、拡張されます。
このモデルでは、各エッジが2ビットの情報を提供し、それぞれのエンドポイントが最適解に属するかどうかの予測に対応する。
各ビットが真の解と相関する$\varepsilon$-であるような弱い予測であっても、この情報は標準設定における近似障壁を破ることができる。
We developed algorithm with improve approximation ratios for MaxCut, Vertex Cover, Set Cover, and Maximum Independent Set problems (and other)。
これらの問題全体で、我々のアルゴリズムは、高次頂点(予測を使わずに)と低次頂点(予測を使わずに)に関連する制約を別々に満たし、答えを慎重に組み合わせる統一的なテーマを共有している。
関連論文リスト
- Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。
我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。
我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
論文 参考訳（メタデータ） (2024-12-03T18:36:45Z) - Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。
我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。
この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文 参考訳（メタデータ） (2024-11-25T17:31:34Z) - Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
我々は,非プライベートなストリーミングと静的アルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。
これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリース$k$-core分解アルゴリズムが含まれる。
論文 参考訳（メタデータ） (2024-07-24T20:15:07Z) - Enhancing Hyperedge Prediction with Context-Aware Self-Supervised Learning [57.35554450622037]
我々は新しいハイパーエッジ予測フレームワーク(CASH)を提案する。
CASHは、コンテキスト認識ノードアグリゲーションを用いて、(C1)ハイパーエッジの各ノード間の複雑な関係をキャプチャし、(2)ハイパーエッジ予測のコンテキストにおける自己教師付きコントラスト学習を行い、(C2)ハイパーグラフ表現を強化する。
6つの実世界のハイパーグラフの実験により、CASHはハイパーエッジ予測の精度で競合する全ての手法を一貫して上回っていることが明らかとなった。
論文 参考訳（メタデータ） (2023-09-11T20:06:00Z) - MAgNet: Mesh Agnostic Neural PDE Solver [68.8204255655161]
気候予測は、流体シミュレーションにおける全ての乱流スケールを解決するために、微細な時間分解能を必要とする。
現在の数値モデル解法 PDEs on grids that too coarse (3km～200km on each side)
本研究では,空間的位置問合せが与えられたPDEの空間的連続解を予測する新しいアーキテクチャを設計する。
論文 参考訳（メタデータ） (2022-10-11T14:52:20Z) - The Neural-Prediction based Acceleration Algorithm of Column Generation
for Graph-Based Set Covering Problems [20.1479227701035]
グラフに基づく集合被覆問題の解法として,ニューラル予測(CG-P)を用いたカラム生成アルゴリズムを提案する。
グラフニューラルネットワークに基づくニューラル予測モデルを用いて,各エッジの最終解に含まれる確率を予測する。
鉄道員のスケジューリング問題に対するCG-Pアルゴリズムの評価を行い,ベースライン列生成アルゴリズムよりも優れていた。
論文 参考訳（メタデータ） (2022-07-04T13:46:59Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。