論文の概要: RamseyRL: A Framework for Intelligent Ramsey Number Counterexample Searching

• arxiv url: http://arxiv.org/abs/2308.11943v1
• Date: Wed, 23 Aug 2023 06:32:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-24 15:26:17.660929
• Title: RamseyRL: A Framework for Intelligent Ramsey Number Counterexample Searching
• Title（参考訳）: RamseyRL: インテリジェントなRamsey数値反例検索フレームワーク
• Authors: Steve Vott, Adam M. Lehavi
• Abstract要約: ラムゼー数はノードの最小数、$n = R(s, t)$ であり、位数 $n$ のすべての無向単純グラフは位数 $s$ あるいは位数 $t$ の独立集合を含む。 本稿では,Ramsey数値に対する反例を見つけるために,最良1次探索アルゴリズムと強化学習(RL)手法の適用について検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Ramsey number is the minimum number of nodes, $n = R(s, t)$, such that all undirected simple graphs of order $n$, contain a clique of order $s$, or an independent set of order $t$. This paper explores the application of a best first search algorithm and reinforcement learning (RL) techniques to find counterexamples to specific Ramsey numbers. We incrementally improve over prior search methods such as random search by introducing a graph vectorization and deep neural network (DNN)-based heuristic, which gauge the likelihood of a graph being a counterexample. The paper also proposes algorithmic optimizations to confine a polynomial search runtime. This paper does not aim to present new counterexamples but rather introduces and evaluates a framework supporting Ramsey counterexample exploration using other heuristics. Code and methods are made available through a PyPI package and GitHub repository.
• Abstract（参考訳）: ラムゼー数 (ramsey number) は最小のノード数で、$n = r(s, t)$ であり、すべての無向単純グラフの順序 $n$ は、順序 $s$ または独立な順序 $t$ を含む。 本稿では,特定のラムゼー数に対する反例を見つけるための最良第一探索アルゴリズムと強化学習(rl)手法の適用について検討する。 グラフベクトル化やディープニューラルネットワーク(DNN)に基づくヒューリスティックを導入し、グラフが逆例である可能性を評価することにより、ランダム検索などの事前探索手法を段階的に改善する。 また,多項式探索ランタイムを限定するアルゴリズム最適化を提案する。 本稿では,新しい反例を提示することではなく,他のヒューリスティックスを用いたラムジー対例探索を支援する枠組みを紹介し,評価する。 コードとメソッドは、PyPIパッケージとGitHubリポジトリを通じて利用できる。

関連論文リスト

• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。 この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
  論文  参考訳（メタデータ） (2024-06-26T18:19:10Z)
• Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
  本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。 この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。 我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-02-27T18:12:58Z)
• Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search [31.68823192070739]
  この研究は、1975年のエルドホスの予想から着想を得た中心極端グラフ理論の問題を研究する。 それは、与えられた大きさ(ノード数)のグラフを見つけることを目的としており、3サイクルや4サイクルを必要とせずに、エッジの数を最大化する。
  論文  参考訳（メタデータ） (2023-11-06T22:29:55Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Verification and search algorithms for causal DAGs [11.038866111306728]
  クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。 我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。 この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-30T15:52:30Z)
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning [1.52292571922932]
  本稿では,グラフニューラルネットワークに基づくアルゴリズムであるPYGONについて述べる。 我々はPYGONが$Thetaleft(sqrtnright)$を復元できることを示し、$n$は背景グラフのサイズである。 また、同じアルゴリズムで、$Thetaleft(sqrtnright)$の複数の植字されたサブグラフを、有向および無向の両方で復元できることを示す。
  論文  参考訳（メタデータ） (2022-01-05T21:11:23Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。 低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
  論文  参考訳（メタデータ） (2020-10-13T17:26:09Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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