論文の概要: Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

• arxiv url: http://arxiv.org/abs/2609.07204v1
• Date: Mon, 07 Sep 2026 08:26:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.388299
• Title: Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts
• Title（参考訳）: エージェントアルゴリズムエンジニアリング:共有メモリのエクササイズ最小化の改善
• Abstract要約: 非方向エッジ重み付きグラフの最小カット問題は、カットエッジの重み付け和を最小化しながら、ノードの集合を2ブロックに分割するように要求する。 我々の最も高速な正確なアルゴリズムは、問題に対するより良いバウンダリを得るために不正確なアルゴリズムを使用します。 オープンソースパッケージのVieCutで利用可能であり、実世界のインスタンスでは、並列実行時に2.5倍、最大12.9倍の速度で、それまでの最速の解決器を上回っている。
• 参考スコア（独自算出の注目度）: 41.19401563581682
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel. We improve this algorithm using agentic algorithm engineering (AAE), a methodology that we introduce here, in which autonomous large language model agents run the algorithm engineering cycle on an existing code base: they form hypotheses about where running time is lost, implement them, benchmark the result on a fixed instance set and keep or discard the change. Even though we had already tuned our algorithm by hand extensively, the agent finds significant optimizations, in particular on the DIMACS core instances: factors of 1.28 (sequential) and 1.63 (32 threads) on real-world k-cores, and 6.26 and 127 on the DIMACS core instances.
• Abstract（参考訳）: 非方向エッジ重み付きグラフの最小カット問題は、カットエッジの重み付け和を最小化しながら、ノードの集合を2ブロックに分割するように要求する。 ここ数年、この問題に対してさまざまな高速アルゴリズムを設計してきました。 我々の最も高速な正確なアルゴリズムは、問題に対するより良いバウンダリ、このバウンダリに依存した削減、改善されたデータ構造、並列収縮ルーチンを得るために不正確なアルゴリズムを使用する。 オープンソースパッケージのVieCutで利用可能であり、実世界のインスタンスでは、並列実行時に2.5倍、最大12.9倍の速度で、それまでの最速の解決器を上回っている。 我々はエージェント・アルゴリズム・エンジニアリング(AAE)を用いてこのアルゴリズムを改善した。これは、自律的な大規模言語モデルエージェントが既存のコードベースでアルゴリズム・エンジニアリング・サイクルを実行する手法である。 すでに手動でアルゴリズムを調整していたが、特にDIMACSコアインスタンスでは、現実世界のkコアでは1.28(シークエンシャル)と1.63(32スレッド)、DIMACSコアインスタンスでは6.26と127という大きな最適化がなされている。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• GPU-accelerated Faster Mean Shift with euclidean distance metrics [1.3507758562554621]
  平均シフトアルゴリズムはクラスタリング問題の解法として広く用いられている。 従来の研究では,GPUを高速化する高速平均シフトアルゴリズムが提案されている。 本研究では,ユークリッド距離測定値を扱うために,従来のアルゴリズムを拡張し改良する。
  論文  参考訳（メタデータ） (2021-12-27T20:18:24Z)
• RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
  本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。 我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。 最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-04T10:33:59Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。 我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
  論文  参考訳（メタデータ） (2021-04-02T16:05:00Z)
• Towards Solving Large-scale Expensive Optimization Problems Efficiently Using Coordinate Descent Algorithm [3.1600708674008393]
  計算予算が限られているLSEGO問題に対処するために,修正された座標 Descent アルゴリズム (MCD) を提案する。 提案アルゴリズムは,関心領域の探索と,指数速度で半分に折り畳むことで検索空間の縮小という,2つの主要なステップの恩恵を受ける。 提案アルゴリズムは,次元1000の20個のベンチマーク関数上でのデルタグルーピングと協調的共進化との比較を行った。
  論文  参考訳（メタデータ） (2020-03-07T22:48:38Z)

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

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