論文の概要: Streaming Submodular Maximization under a $k$-Set System Constraint

• arxiv url: http://arxiv.org/abs/2002.03352v1
• Date: Sun, 9 Feb 2020 12:32:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-02 14:52:03.748538
• Title: Streaming Submodular Maximization under a $k$-Set System Constraint
• Title（参考訳）: $k$-set 制約下でのストリーミングサブモジュラー最大化
• Authors: Ran Haba, Ehsan Kazemi, Moran Feldman and Amin Karbasi
• Abstract要約: 非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。 また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 42.31117997337689
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a novel framework that converts streaming algorithms for monotone submodular maximization into streaming algorithms for non-monotone submodular maximization. This reduction readily leads to the currently tightest deterministic approximation ratio for submodular maximization subject to a $k$-matchoid constraint. Moreover, we propose the first streaming algorithm for monotone submodular maximization subject to $k$-extendible and $k$-set system constraints. Together with our proposed reduction, we obtain $O(k\log k)$ and $O(k^2\log k)$ approximation ratio for submodular maximization subject to the above constraints, respectively. We extensively evaluate the empirical performance of our algorithm against the existing work in a series of experiments including finding the maximum independent set in randomly generated graphs, maximizing linear functions over social networks, movie recommendation, Yelp location summarization, and Twitter data summarization.
• Abstract（参考訳）: 本稿では,モノトンサブモジュラー最大化のためのストリーミングアルゴリズムを非モノトンサブモジュラー最大化のためのストリーミングアルゴリズムに変換する新しいフレームワークを提案する。 この還元は容易に$k$-matchoid制約を受ける部分モジュラー最大化に対する現在最も厳密な決定論的近似比をもたらす。 さらに,$k$-extendible と $k$-set の制約を受けるモノトーンサブモジュラー最大化のための最初のストリーミングアルゴリズムを提案する。 提案する還元法とともに,上記の制約を満たす部分モジュラー最大化の近似比として,o(k\log k)$ と $o(k^2\log k)$ を得る。 我々は,ランダムに生成されたグラフにおける最大独立集合の探索,ソーシャルネットワーク上の線形関数の最大化,映画推薦,yelp位置要約,twitterデータの要約など,既存の作業に対するアルゴリズムの実証的性能を広範囲に評価した。

関連論文リスト

• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Dynamic Non-monotone Submodular Maximization [11.354502646593607]
  濃度制約$k$で非単調部分モジュラ函数を最大化することから、同じ制約の下で単調部分モジュラ函数を最大化することへの還元を示す。 我々のアルゴリズムは、ソリューションの$(epsilon)$-approximateを維持し、期待される$O(epsilon-3k3log3(n)log(k)$ query per updateを使用する。
  論文  参考訳（メタデータ） (2023-11-07T03:20:02Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
  差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。 マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-28T23:18:58Z)
• Submodular Maximization in Clean Linear Time [42.51873363778082]
  我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。 解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。 我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
  論文  参考訳（メタデータ） (2020-06-16T17:06:45Z)
• Submodular Maximization Through Barrier Functions [32.41824379833395]
  連続最適化における障壁関数に着想を得た制約付き部分モジュラーの新しい手法を提案する。 提案するアルゴリズムを実世界の複数のアプリケーションに対して広範囲に評価する。
  論文  参考訳（メタデータ） (2020-02-10T03:32:49Z)

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

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