論文の概要: Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms

• arxiv url: http://arxiv.org/abs/2006.12773v2
• Date: Tue, 8 Sep 2020 06:31:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 21:40:12.593414
• Title: Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
• Title（参考訳）: 多目的進化アルゴリズムによる分割マトロイド制約下でのサブモジュラーまたはモノトン関数の最大化
• Authors: Anh Viet Do, Frank Neumann
• Abstract要約: GSEMOと呼ばれる単純な進化的アルゴリズムは、部分モジュラ函数の近似を効率的に行うことが示されている。 我々は理論結果を拡張し、濃度制約を一般化するマトロイド制約を分割する。
• 参考スコア（独自算出の注目度）: 16.691265882753346
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many important problems can be regarded as maximizing submodular functions under some constraints. A simple multi-objective evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodular functions efficiently. While there have been many studies on the subject, most of existing run-time analyses for GSEMO assume a single cardinality constraint. In this work, we extend the theoretical results to partition matroid constraints which generalize cardinality constraints, and show that GSEMO can generally guarantee good approximation performance within polynomial expected run time. Furthermore, we conducted experimental comparison against a baseline GREEDY algorithm in maximizing undirected graph cuts on random graphs, under various partition matroid constraints. The results show GSEMO tends to outperform GREEDY in quadratic run time.
• Abstract（参考訳）: 多くの重要な問題は、いくつかの制約の下でサブモジュラー関数を最大化することと見なすことができる。 GSEMOと呼ばれる単純な多目的進化アルゴリズムは、部分モジュラ函数の近似を効率的に行うことが示されている。 この問題については多くの研究がなされているが、既存のGSEMOのランタイム分析のほとんどは単一の濃度制約を仮定している。 本研究では,集合的制約を一般化するmatroid制約を分割する理論結果を拡張し,gsemoが一般的に多項式の期待実行時間内での近似性能を保証できることを示す。 さらに,様々な分割マトロイド制約下でランダムグラフ上の無向グラフカットを最大化するために,ベースライングリーディアルゴリズムに対する実験的比較を行った。 GSEMOは2次実行時間でGREEDYを上回る傾向を示した。

関連論文リスト

• Sliding Window Bi-Objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular Functions [10.506038775815094]
  本稿では,[21]で導入されたスライディング・セレクションのアプローチを,確率制約付き単調部分モジュラ関数の最適化に適用する。 SW-GSEMOアルゴリズムは,実行環境に影響を及ぼす重要な要因として,個体数制限に成功していることを示す。
  論文  参考訳（メタデータ） (2024-07-13T00:28:29Z)
• Submodular Maximization under the Intersection of Matroid and Knapsack Constraints [23.0838604893412]
  我々は、よく使われる2つの制約、すなわち$k$matroid 制約と $m$-knapsack 制約の交わる部分モジュラー演算の問題を考察する。 我々は、SPROUTOUTが最先端のアルゴリズムを組み込むよりも、SPR時間近似の保証を実現できることを証明した。 映画レコメンデーションと重み付きマックスカットの応用実験は、実際にSPROUT++の優位性を実証している。
  論文  参考訳（メタデータ） (2023-07-18T02:37:14Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences [44.11102526976392]
  本稿では,シーケンス上のモノトーン部分モジュラ関数を最大化する問題クラスについて検討する。 EAは、部分モジュラ最適化の問題を解くための優れた近似保証を達成できる。 例えば、タスクの達成、情報ゲインの最大化、探索と追跡、レコメンデーションシステムなど、様々なアプリケーションに関する実証研究は、GSEMOの優れた性能を示している。
  論文  参考訳（メタデータ） (2021-04-20T10:36:10Z)
• Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [11.807734722701786]
  ここでは制約は成分を伴い、制約はアルファの小さな確率でのみ破ることができる。 GSEMOアルゴリズムは, 単調な部分モジュラ関数に対して, 最悪の性能保証が得られることを示す。 実験結果から, 進化的多目的アルゴリズムを用いることで, 性能が大幅に向上することが示唆された。
  論文  参考訳（メタデータ） (2020-06-20T00:17:44Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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