論文の概要: Structural Segmentation of the Minimum Set Cover Problem: Exploiting Universe Decomposability for Metaheuristic Optimization

• arxiv url: http://arxiv.org/abs/2604.03234v1
• Date: Thu, 29 Jan 2026 14:02:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-19 19:09:11.339446
• Title: Structural Segmentation of the Minimum Set Cover Problem: Exploiting Universe Decomposability for Metaheuristic Optimization
• Title（参考訳）: 最小集合被覆問題の構造分割:メタヒューリスティック最適化のための宇宙分解可能性の爆発
• Authors: Isidora Hernández, Héctor Ferrada, Cristóbal A. Navarro,
• Abstract要約: 最小設定被覆問題(英: Minimum Set Cover Problem、MSCP)は、科学と工学に多くの応用がある古典的なNPハード最適化問題である。 本研究は,MSCPにおける直交セグメント性の概念を考察し,本質的な構造的分解をどのように活用して本質的な最適化を向上するかを考察する。
• 参考スコア（独自算出の注目度）: 1.1011268090482575
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Minimum Set Cover Problem (MSCP) is a classical NP-hard combinatorial optimization problem with numerous applications in science and engineering. Although a wide range of exact, approximate, and metaheuristic approaches have been proposed, most methods implicitly treat MSCP instances as monolithic, overlooking potential intrinsic structural properties of the universe. In this work, we investigate the concept of \emph{universe segmentability} in the MSCP and analyze how intrinsic structural decomposition (universe segmentability) can be exploited to enhance heuristic optimization. We propose an efficient preprocessing strategy based on disjoint-set union (union--find) to detect connected components induced by element co-occurrence within subsets, enabling the decomposition of the original instance into independent subproblems. Each subproblem is solved using the GRASP metaheuristic, and partial solutions are combined without compromising feasibility. Extensive experiments on standard benchmark instances and large-scale synthetic datasets show that exploiting natural universe segmentation consistently improves solution quality and scalability, particularly for large and structurally decomposable instances. These gains are supported by a succinct bit-level set representation that enables efficient set operations, making the proposed approach computationally practical at scale.
• Abstract（参考訳）: 最小集合被覆問題(英: Minimum Set Cover Problem、MSCP)は、科学と工学における多くの応用を持つ古典的なNPハード組合せ最適化問題である。 幅広い正確で近似的でメタヒューリスティックなアプローチが提案されているが、ほとんどの手法はMSCPのインスタンスを暗黙的にモノリシックとして扱い、宇宙の潜在的な内在的な構造的特性を見越す。 本研究では,MSCPにおけるemph{universe segmentability}の概念を考察し,本質的な構造的分解(一様セグメンタビリティ)をどのように利用してヒューリスティックな最適化を向上するかを考察する。 本稿では、部分集合内の要素共起によって引き起こされる連結成分を検出するために、解離集合和(ユニオンフィン)に基づく効率的な前処理戦略を提案し、元のインスタンスを独立サブプロブレムに分解できるようにする。 各サブプロブレムはGRASPメタヒューリスティックを用いて解かれ、部分解は実現性を損なうことなく組み合わせられる。 標準ベンチマークインスタンスと大規模合成データセットの大規模な実験は、特に大規模で構造的に分解可能なインスタンスにおいて、自然界のセグメンテーションを活用することにより、ソリューションの品質とスケーラビリティが一貫して向上することを示している。 これらの利得は、効率的な集合演算を可能にする簡潔なビットレベル集合表現によって支えられ、提案手法は大規模に計算学的に実用的である。

関連論文リスト

• STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization [18.162186876640764]
  演算研究と理論計算機科学の中心となる組合せ最適化(CO)問題は、NPハードな性質のため、重要な計算課題を提示する。 本稿では,StRCMPを提案する。STRCMPは,構造先行を体系的に統合し,解の質と解解効率を向上する新しい構造対応アルゴリズム探索フレームワークである。 我々のフレームワークは、COインスタンスから構造埋め込みを抽出するグラフニューラルネットワーク(GNN)と、これらの埋め込みを条件としたLLMを組み合わせることで、ソルバ固有コードの形で高い性能のアルゴリズムを識別する。
  論文  参考訳（メタデータ） (2025-05-22T15:37:42Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  我々はスムーズな(摂動された)ポリシーを解析し、線形オラクルが使用する方向に対して制御されたランダムな摂動を付加する。 我々の主な貢献は、過剰リスクを摂動バイアス、統計的推定誤差、最適化誤差に分解する一般化境界である。 車両のスケジューリングやスムーズ化がトラクタブルトレーニングと制御された一般化の両方を可能にしていることを示す。
  論文  参考訳（メタデータ） (2024-07-24T12:00:30Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems [5.099537069575897]
  非負・正の行列とテンソル完備問題を定義・解決するための新しい一貫性に基づくアプローチを導入する。 単一特性/制約: 単位スケールの一貫性を保ち、解の存在を保証し、比較的弱いサポート仮定の下では、一意性を示す。
  論文  参考訳（メタデータ） (2022-04-04T19:42:46Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)

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

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