論文の概要: Multilevel Memetic Hypergraph Partitioning with Greedy Recombination
- arxiv url: http://arxiv.org/abs/2204.03730v1
- Date: Thu, 7 Apr 2022 20:45:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 23:47:51.273901
- Title: Multilevel Memetic Hypergraph Partitioning with Greedy Recombination
- Title（参考訳）: グリーディ組換えを伴う多レベルmemetic hypergraphパーティショニング
- Authors: Utku Umur Acikalin, Bugra Caskurlu
- Abstract要約: KaHyPar-Eはハイパーグラフ分割問題のために設計された最初のマルチレベルメメティック計算アルゴリズムである。
問題固有のリコンビネーションと突然変異演算子を導入し,KaHyPar-Eとそれらの演算子を組み合わせることで,新しいマルチレベルメメティックアルゴリズムを開発した。
我々のアルゴリズムは他のすべてより優れていて、最高のソリューションは12ドル、15ドル、25ドル、それぞれ2ドル、4ドル、そして8ドルだ。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Hypergraph Partitioning (HGP) problem is a well-studied problem that
finds applications in a variety of domains. The literature on the HGP problem
has heavily focused on developing fast heuristic approaches. In several
application domains, such as the VLSI design and database migration planning,
the quality of the solution is more of a concern than the running time of the
algorithm. KaHyPar-E is the first multilevel memetic algorithm designed for the
HGP problem and it returns better quality solutions, compared to the heuristic
algorithms, if sufficient computation time is given. In this work, we introduce
novel problem-specific recombination and mutation operators, and develop a new
multilevel memetic algorithm by combining KaHyPar-E with these operators. The
performance of our algorithm is compared with the state-of-the-art HGP
algorithms on $150$ real-life instances taken from the benchmark datasets used
in the literature. In the experiments, which would take $39,000$ hours in a
single-core computer, each algorithm is given $2, 4$, and $8$ hours to compute
a solution for each instance. Our algorithm outperforms all others and finds
the best solutions in $112$, $115$, and $125$ instances in $2, 4$, and $8$
hours, respectively.
- Abstract（参考訳）: ハイパーグラフ分割問題(HGP)は、様々な分野の応用をよく研究する問題である。
HGP問題に関する文献は、高速ヒューリスティックなアプローチの開発に重点を置いている。
VLSI設計やデータベースマイグレーション計画といったいくつかのアプリケーション領域では、ソリューションの品質はアルゴリズムの実行時間よりも懸念される。
KaHyPar-EはHGP問題のために設計された最初のマルチレベルメメティックアルゴリズムであり、十分な計算時間を与えられた場合のヒューリスティックアルゴリズムと比較して、より良い品質の解を返す。
本研究では,新しい問題固有組換えと突然変異演算子を導入し,KaHyPar-Eとそれらの演算子を組み合わせることで,新しいマルチレベルメメティックアルゴリズムを開発した。
このアルゴリズムの性能は、文献で使われているベンチマークデータセットから取られた150ドルの実生活インスタンスにおける最先端のhgpアルゴリズムと比較される。
シングルコアコンピュータで39,000ドルを要した実験では、各アルゴリズムは各インスタンスの解を計算するのに2ドル、4ドル、そして8ドルを与えられる。
われわれのアルゴリズムは他よりも優れていて、ベストなソリューションは12ドル、115ドル、125ドルのインスタンスはそれぞれ2ドル、4ドル、8ドルだ。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Unlocking the Potential of Operations Research for Multi-Graph Matching [14.3836693915104]
マルチグラフマッチングはコンピュータビジョンにおいて、例えば画像や形状のマッチングにおいて中心的な役割を果たす。
我々はMDAPのよく知られた近似アルゴリズムを不完全な多重グラフマッチングに転送する。
私たちのアルゴリズムは、2分以内でそれぞれ500以上のキーポイントを持つ29の画像と一致します。
論文 参考訳（メタデータ） (2024-06-26T09:58:05Z) - EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
EKM: 最悪の$Oleft(NK+1right)$複雑性でこの問題を正確に解くための新しいアルゴリズムを提案する。
EKMは、フォーマルなプログラムステップを用いて、変換プログラミングと生成の最近の進歩に従って開発されている。
我々は,アルゴリズムのウォールタイム実行時間が,合成データセット上での最悪の時間複雑性解析と一致することを示した。
論文 参考訳（メタデータ） (2024-05-16T15:11:37Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Combining K-means type algorithms with Hill Climbing for Joint
Stratification and Sample Allocation Designs [0.0]
これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。
それぞれのソリューションのコストを評価するのに 費用がかかります
上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
論文 参考訳（メタデータ） (2021-08-18T08:41:58Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Towards Solving Large-scale Expensive Optimization Problems Efficiently
Using Coordinate Descent Algorithm [3.1600708674008393]
計算予算が限られているLSEGO問題に対処するために,修正された座標 Descent アルゴリズム (MCD) を提案する。
提案アルゴリズムは,関心領域の探索と,指数速度で半分に折り畳むことで検索空間の縮小という,2つの主要なステップの恩恵を受ける。
提案アルゴリズムは,次元1000の20個のベンチマーク関数上でのデルタグルーピングと協調的共進化との比較を行った。
論文 参考訳（メタデータ） (2020-03-07T22:48:38Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。