論文の概要: Wave Function Collapse Set Covering and the Hill Climbing Algorithm: A New, Fast Heuristic and Metaheuristic Pairing for the Minimum Set Cover Problem
- arxiv url: http://arxiv.org/abs/2509.12236v1
- Date: Tue, 09 Sep 2025 01:28:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-17 17:50:52.6329
- Title: Wave Function Collapse Set Covering and the Hill Climbing Algorithm: A New, Fast Heuristic and Metaheuristic Pairing for the Minimum Set Cover Problem
- Title（参考訳）: Wave Function Collapse Set Covering and the Hill Climbing Algorithm: A New, Fast Heuristic and Metaheuristic Pairing for the Minimum Set Cover Problem
- Authors: David Oprea, David Perkins,
- Abstract要約: 本稿では,最小設定被覆問題に対する最適化問題に焦点をあてる関数を提案する。
このアルゴリズムは観察、伝播、崩壊を経る。
ブルネル大学の有名なORライブラリを、他の有能なアルゴリズムと比較して、アルゴリズムをベンチマークする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we present a new heuristic that focuses on the optimization problem for the Minimum Set Cover Problem. Our new heuristic involves using Wave Function Collapse and is called Wave Function Collapse Set Covering (WFC-SC). This algorithm goes through observation, propagation, and collapsing, which will be explained more later on in this paper. We optimize this algorithm to quickly find optimal coverings that are close to the minimum needed. To further optimize this algorithm, we pair it with the Hill Climbing metaheuristic to help WFC-SC find a better solution than its "local optimum." We benchmark our algorithm using the well known OR library from Brunel University against other proficient algorithms. We find that our algorithm has a better balance between both optimality and time.
- Abstract（参考訳）: 本稿では,最小設定被覆問題に対する最適化問題に着目した新しいヒューリスティックを提案する。
我々の新しいヒューリスティックはWave Function Collapseを使用し、Wave Function Collapse Set Covering (WFC-SC)と呼ばれる。
このアルゴリズムは観測、伝播、崩壊を経ており、この論文ではさらに後述する。
我々はこのアルゴリズムを最適化し、必要な最小値に近い最適被覆を素早く見つける。
このアルゴリズムをさらに最適化するために、Hill Climbingメタヒューリスティックと組み合わせて、WFC-SCの「局所最適化」よりも優れた解を見つけるのに役立つ。
ブルネル大学の有名なORライブラリを、他の有能なアルゴリズムと比較して、アルゴリズムをベンチマークする。
我々のアルゴリズムは最適性と時間の両方のバランスが良いことがわかった。
関連論文リスト
- Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。
我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。
この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文 参考訳（メタデータ） (2024-11-25T17:31:34Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
本稿では,候補アルゴリズムの集合に有効な手法を提案する。
内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。
提案手法は,他のアルゴリズムのスコアを大幅に改善する。
論文 参考訳（メタデータ） (2023-05-26T21:49:37Z) - Smoothed Analysis of Sequential Probability Assignment [16.090378928208885]
本稿では,情報理論的に最適であるminmaxレートと,最大極大推定器オラクルを含むアルゴリズム削減の枠組みについて検討する。
提案手法は,スムーズな逆数に対する逐次確率割当のためのミニマックスレートから,トランスダクティブ学習のためのミニマックスレートへの汎用的な削減を実現する。
論文 参考訳（メタデータ） (2023-03-08T19:25:57Z) - Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization [17.467589890017123]
本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
コンベックスコンケーブ・コンケーブの両ケースにおいて, RAIN (SFO) が最小限の最適化を実現することを示す。
論文 参考訳（メタデータ） (2022-08-11T16:55:26Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。