論文の概要: Maximizing approximately k-submodular functions

• arxiv url: http://arxiv.org/abs/2101.07157v1
• Date: Mon, 18 Jan 2021 16:48:40 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-27 11:05:08.372517
• Title: Maximizing approximately k-submodular functions
• Title（参考訳）: 近似k-部分モジュラー関数の最大化
• Authors: Leqian Zheng and Hau Chan and Grigorios Loukides and Minming Li
• Abstract要約: サイズ制約を考慮した$k$-submodular関数の最大化の問題を導入する。 問題は、センサー配置などのタスクでアプリケーションを見つけます。 単純な欲望アルゴリズムは、異なる種類のサイズ制約に対して近似保証を提供する。
• 参考スコア（独自算出の注目度）: 21.881345069785105
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the problem of maximizing approximately $k$-submodular functions subject to size constraints. In this problem, one seeks to select $k$-disjoint subsets of a ground set with bounded total size or individual sizes, and maximum utility, given by a function that is "close" to being $k$-submodular. The problem finds applications in tasks such as sensor placement, where one wishes to install $k$ types of sensors whose measurements are noisy, and influence maximization, where one seeks to advertise $k$ topics to users of a social network whose level of influence is uncertain. To deal with the problem, we first provide two natural definitions for approximately $k$-submodular functions and establish a hierarchical relationship between them. Next, we show that simple greedy algorithms offer approximation guarantees for different types of size constraints. Last, we demonstrate experimentally that the greedy algorithms are effective in sensor placement and influence maximization problems.
• Abstract（参考訳）: サイズ制約を受ける約$k$-サブモジュラー関数を最大化する問題を導入する。 この問題では、有界な総サイズまたは個々のサイズを持つ基底集合の$k$-disjoint部分集合と、$k$-submodular となる関数の "close" によって与えられる最大効用を選ぼうとする。 この問題は、ノイズの多いセンサのタイプに$k$をインストールしたいというセンサー配置や、影響力のレベルが不確実なソーシャルネットワークのユーザに$k$のトピックを宣伝しようとしている最大化などのタスクに応用されている。 この問題に対処するために、我々はまず、約$k$-submodular関数に対する2つの自然な定義を提供し、それらの間の階層的関係を確立する。 次に, 単純な欲望アルゴリズムが, 異なるサイズ制約に対する近似保証を提供することを示す。 最後に,このアルゴリズムがセンサ配置や最大化問題に有効であることを実験的に示す。

関連論文リスト

• 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)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。 近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。 ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
  論文  参考訳（メタデータ） (2023-09-21T21:51:55Z)
• Balancing Utility and Fairness in Submodular Maximization (Technical Report) [27.20340546154524]
  実用性と公平性のバランスをとるために,emphBi Maxim Submodularization (BSM) と呼ばれる新しい問題を提案する。 BSMは任意の定数係数で近似できないため、効率的なインスタンス依存近似スキームの設計に焦点をあてる。
  論文  参考訳（メタデータ） (2022-11-02T09:38:08Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Fair and Representative Subset Selection from Data Streams [4.53279507109072]
  ストリーム内のデータ項目が複数の不随意群に属する設定について検討する。 ストリーミングサブモジュラー問題の公平性を考慮した変種に対する効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-09T07:49:13Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• 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 Through Barrier Functions [32.41824379833395]
  連続最適化における障壁関数に着想を得た制約付き部分モジュラーの新しい手法を提案する。 提案するアルゴリズムを実世界の複数のアプリケーションに対して広範囲に評価する。
  論文  参考訳（メタデータ） (2020-02-10T03:32:49Z)

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

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