論文の概要: An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem

• arxiv url: http://arxiv.org/abs/2402.03736v1
• Date: Tue, 6 Feb 2024 06:05:11 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-07 16:18:54.282640
• Title: An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
• Title（参考訳）: 最大$s$-bundle問題に対する新しい境界法を用いた効果的な分岐・境界アルゴリズム
• Authors: Jinghui Xue, Jiongzhi Zheng, Mingming Jin and Kun He
• Abstract要約: 最大s束問題(英: Maximum s-Bundle Problem、MBP)は、与えられたグラフ内の最大s束を特定するタスクに対処する問題である。 本稿では,グラフ分割技術を利用した分割型アッパーバウンド(PUB)を導入し,より厳密なアッパーバウンドを実現する。 また,グラフ削減のための前処理において,初期下界とPUBを利用する新しいBnBアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 9.400610985728441
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Maximum s-Bundle Problem (MBP) addresses the task of identifying a maximum s-bundle in a given graph. A graph G=(V, E) is called an s-bundle if its vertex connectivity is at least |V|-s, where the vertex connectivity equals the minimum number of vertices whose deletion yields a disconnected or trivial graph. MBP is NP-hard and holds relevance in numerous realworld scenarios emphasizing the vertex connectivity. Exact algorithms for MBP mainly follow the branch-and-bound (BnB) framework, whose performance heavily depends on the quality of the upper bound on the cardinality of a maximum s-bundle and the initial lower bound with graph reduction. In this work, we introduce a novel Partition-based Upper Bound (PUB) that leverages the graph partitioning technique to achieve a tighter upper bound compared to existing ones. To increase the lower bound, we propose to do short random walks on a clique to generate larger initial solutions. Then, we propose a new BnB algorithm that uses the initial lower bound and PUB in preprocessing for graph reduction, and uses PUB in the BnB search process for branch pruning. Extensive experiments with diverse s values demonstrate the significant progress of our algorithm over state-of-the-art BnB MBP algorithms. Moreover, our initial lower bound can also be generalized to other relaxation clique problems.
• Abstract（参考訳）: 最大sバンドル問題(MBP)は、与えられたグラフ内の最大sバンドルを特定するタスクに対処する。 グラフ g=(v, e) が s-バンドル (s-bundle) とは、頂点接続が少なくとも |v|-s であるとき、頂点接続が最小の頂点数に等しいときに言う。 MBPはNPハードであり、頂点接続性を強調する多くの現実シナリオに関連がある。 mbpの正確なアルゴリズムは、主に分枝結合(bnb)フレームワークに従っており、その性能は最大s束の濃度とグラフ還元による最初の下限の上限の品質に大きく依存している。 本研究では,グラフ分割技術を活用した分割型上界(PUB)を導入し,既存のものに比べてより厳密な上界を実現する。 下限を増加させるために,クリップ上で短いランダムウォークを行い,より大きな初期解を生成することを提案する。 そこで我々は,グラフ削減のための前処理に初期下界とPUBを用いる新しいBnBアルゴリズムを提案し,分岐解析にBnB探索プロセスにPUBを用いる。 多様なs値を用いた大規模な実験は、最先端のBnB MBPアルゴリズムに対する我々のアルゴリズムの顕著な進歩を示している。 さらに、最初の下界は、他の緩和傾斜問題にも一般化できる。

関連論文リスト

• BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs [0.3277163122167434]
  本稿では,二部グラフ内の最大双斜線を包括的に列挙するアルゴリズムを提案する。 BBK for Bipartite Bron-Kerboschと呼ばれるこのアルゴリズムは、Bron-Kerboschアルゴリズムの新しい拡張である。 最先端のアルゴリズムよりも高速で、既存の実装では管理できない巨大な二部グラフの列挙を可能にする。
  論文  参考訳（メタデータ） (2024-05-07T15:49:34Z)
• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。 まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。 補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
  論文  参考訳（メタデータ） (2024-04-24T18:39:18Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Hybrid Learning with New Value Function for the Maximum Common Subgraph Problem [17.08436177950109]
  ブランチ・アンド・バウンド(BnB)は、最大共通誘導部分グラフ(MCS)のための効率的なアルゴリズムのクラスの基礎である MCSのための新しいBnBアルゴリズムであるMcSplitDALを定義するために、強化学習に使用される新しい値関数とハイブリッド選択戦略を提案する。
  論文  参考訳（メタデータ） (2022-08-18T03:43:50Z)
• Multi-Stage Graph Peeling Algorithm for Probabilistic Core Decomposition [3.004067332389205]
  最近Esfahaniらは、グラフの剥離と中央極限定理(CLT)に基づく確率的コア分解アルゴリズムを発表した。 本稿では,前回のPAの前に2段階のデータスクリーニング処理を付加したマルチステージグラフ剥離アルゴリズム(M-PA)を提案する。 我々は,M-PAが従来のPAよりも効率的であり,適切に設定されたフィルタリングしきい値により,従来のPAと非常によく似た密度のサブグラフを生成することを示す。
  論文  参考訳（メタデータ） (2021-08-13T07:06:32Z)
• Causal Bandits on General Graphs [1.4502611532302039]
  本稿では、因果グラフのみによって指定された因果ベイズネットワーク(CBN)における最良の介入を決定する問題について検討する。 本稿では,原子間干渉や観測不可能な変数を含む半マルコフ因果グラフを入力として用いた,簡単な後悔最小化アルゴリズムを提案する。 この結果から,提案アルゴリズムの単純後悔保証は,因果グラフのより微妙な構造的制約を考慮すれば改善できることがわかった。
  論文  参考訳（メタデータ） (2021-07-06T17:29:45Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)
• GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
  我々は,最も困難なブラックボックス設定の1つにおいて,逆例を生成するためのフレームワークを提案する。 我々のフレームワークは、ディープネットワークの決定境界は通常、データサンプルの近傍で小さな平均曲率を持つという観察に基づいている。
  論文  参考訳（メタデータ） (2020-03-13T20:03:01Z)

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

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