論文の概要: Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates

• arxiv url: http://arxiv.org/abs/2609.17951v1
• Date: Wed, 16 Sep 2026 00:23:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.578524
• Title: Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates
• Title（参考訳）: ハイパーグラフの最大独立集合:還元、境界、グリーディ証明書
• Abstract要約: 有限ハイパーグラフにおける最大強独立集合問題について検討する。 本稿では,この問題に対する入射構造ツールキットを開発した。 アルゴリズム解析には、実現可能性、最大性、条件最適性、階層化された目撃者マッチング上界、入射局所複雑性境界が含まれる。
• 参考スコア（独自算出の注目度）: 7.711757703549023
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the maximum strong independent set problem in a finite hypergraph: find the largest vertex set that intersects every hyperedge in at most one vertex. This objective arises whenever each observed block is a local incompatibility constraint but transitive closure across overlapping blocks is not justified. A motivating example is multi-band LSH-MinHash deduplication, where each collision bucket gives local evidence, while connected-component contraction can impose spurious global equivalences. The paper develops an incidence-structural toolkit for this problem. We prove exact reductions for dominance, incidence twins, and weight-1 blocks; derive closed-form and low-weight upper bounds; introduce puncturing and covering certificates that sharpen those bounds; and analyze a layered greedy clustering algorithm driven by block weights and residual incidence. The algorithmic analysis includes feasibility, maximality, conditional optimality, a layered witness-matching upper bound, and incidence-local complexity bounds. The results give correctness, termination, fixed-point, and optimality certificates for broad incidence families, together with examples showing when different certificates separate or coincide.
• Abstract（参考訳）: 有限ハイパーグラフにおける最大強独立集合問題について研究し、最大1つの頂点においてすべてのハイパーエッジと交差する最大の頂点集合を求める。 この目的は、各観測ブロックが局所的不整合制約であるが、重なり合うブロック間の推移的閉包が正当化されないときに生じる。 モチベーションの例としてはマルチバンドのLSH-MinHash復号法があり、各衝突バケットが局所的な証拠を与えるが、連結成分の縮約により大域的等価性が生じる。 本稿では,この問題に対する入射構造ツールキットを開発した。 我々は、支配力、インクリメンタルツインダー、ウェイト-1ブロックの正確な削減、クローズドフォームおよびローウェイトオーバーバウンドの導出、それらのバウンドを鋭くする句読・カバー証明書の導入、ブロックウェイトと残差インクリメンタルインクリメントによって駆動される層状グリーディクラスタリングアルゴリズムの解析を証明した。 アルゴリズム解析には、実現可能性、最大性、条件最適性、階層化された目撃者マッチング上界、入射局所的な複雑性境界が含まれる。 結果は、広範囲のインシデント家族に対する正当性、終端性、定点性、最適性証明と、異なる証明書が分離または一致したことを示す例を与える。

関連論文リスト

• Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation [51.56484100374058]
  我々は、ハードレイヤーワイドリプシッツ予算の下で近似を研究する。 構成条件下では、対応するレイヤエラーをキャンセルする必要はないことを示す。 クラスのすべての作用素に対して、安定した深さ-$L$タワーが存在し、累積誤差の定数分を実現できる。
  論文  参考訳（メタデータ） (2026-09-14T20:17:04Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。 理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
  論文  参考訳（メタデータ） (2026-06-30T06:10:25Z)
• Constrained Pareto Set Identification with Bandit Feedback [10.967572582187014]
  意味不明の$Kの武器が与えられた場合、平均が他の腕よりも一様でない腕のセットを特定することが目的である。 我々は固定信頼度同定に重点を置いており、レースのようなアルゴリズムを著しく上回るアルゴリズムを導入している。
  論文  参考訳（メタデータ） (2025-06-09T18:29:28Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models [0.0]
  非一様ハイパーグラフブロックモデル(HSBM)の下でのランダムハイパーグラフの教師なし分類問題 本稿では,クラスタリング精度と強い一貫性しきい値に対する情報理論の限界を確立する。
  論文  参考訳（メタデータ） (2023-06-12T03:38:25Z)
• Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model [0.0]
  非一様ハイパーグラフ化ブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 文献ではじめて、この一様でないケース下での正確な回復のための鋭いしきい値が、小さな制約の下で確立された。 しきい値を超えると正確な回復を達成でき、正確な回復が不可能な場合には最小の確率で達成できる2つの効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-04-25T20:30:33Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。 我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。 具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
  論文  参考訳（メタデータ） (2023-04-18T17:57:31Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。 その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-01-23T16:47:52Z)

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

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