論文の概要: Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

• arxiv url: http://arxiv.org/abs/2002.05477v1
• Date: Thu, 13 Feb 2020 12:33:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-01 13:48:56.733903
• Title: Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Title（参考訳）: ストリーミングモデルにおける濃度とマトロイド制約下でのモノトンサブモジュラー関数の最大化の近似可能性
• Authors: Chien-Chung Huang and Naonori Kakimura and Simon Mauras and Yuichi Yoshida
• Abstract要約: 単一パスストリーミングモデルで1-frac1e$を超える濃度とマトロイドの制約に対する近似比の最初の下限を示す。 近似比が $fracK2K-1$ と $frac12$ であるような基数とマトロイドの制約に対する弱いオーラルストリーミングアルゴリズムを示す。
• 参考スコア（独自算出の注目度）: 22.637004266371545
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is much gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat $1-\frac{1}{e}$ in the single-pass streaming model. Let $n$ be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio $\frac{2}{2+\sqrt{2}}+\varepsilon$ requires $\Omega\left(\frac{n}{K^2}\right)$ space for any $\varepsilon>0$, where $K$ is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio $\frac{K}{2K-1}+\varepsilon$ requires $\Omega\left(\frac{n}{K}\right)$ space for any $\varepsilon>0$, where $K$ is the rank of the given matroid. In addition, we give streaming algorithms when we only have a weak oracle with which we can only evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios $\frac{K}{2K-1}$ and $\frac{1}{2}$, respectively, whose space complexity is exponential in $K$ but is independent of $n$. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of $\frac{K}{2K-1}$ for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of $n$.
• Abstract（参考訳）: 様々な制約の下での単調部分モジュラ函数の最大化は古典的かつ集中的に研究された問題である。 しかし、入力要素が1個ずつ到着し、アルゴリズムが少数の入力要素しか格納できないシングルパスストリーミングモデルでは、文献でいくつかの近似アルゴリズムが提案されているにもかかわらず、我々の知識には大きなギャップがある。 本研究では,1-\frac{1}{e}$を1パスのストリーミングモデルで上回った濃度とマトロイドの制約に対する近似比の最初の下界を示す。 n$をストリーム内の要素の数とする。 次に、近似比 $\frac{2}{2+\sqrt{2}}+\varepsilon$ を持つ濃度制約に対する任意の(ランダム化された)ストリーミングアルゴリズムは、$\varepsilon>0$ に対して$\omega\left(\frac{n}{k^2}\right)$空間を必要とし、ここで $k$ は出力集合のサイズ制限である。 また、近似比 $\frac{k}{2k-1}+\varepsilon$ を持つ(分割された)マトロイド制約に対する任意の(ランダム化された)ストリーミングアルゴリズムは、任意の $\varepsilon>0$ に対して $\omega\left(\frac{n}{k}\right)$ space を必要とし、ここで $k$ は与えられたマトロイドのランクである。 さらに,弱いオラクルしか持たない場合,実現可能な集合上の関数値のみを評価可能なストリーミングアルゴリズムを提案する。 具体的には、近似比が$\frac{k}{2k-1}$と$\frac{1}{2}$であるような濃度とマトロイド制約に対する弱いoracleのストリーミングアルゴリズムを示し、その空間複雑性は$k$で指数関数的だが$n$とは独立である。 前者は弱オラクルモデルにおける濃度制約に対する既知の不近似結果と正確に一致する。 後者は、matroid制約に対する$\frac{k}{2k-1}$の下限にほぼ一致する。これは、空間複雑性が$n$から独立なストリーミングアルゴリズムによって得られるmatroid制約の近似比をほぼ解決するものである。

関連論文リスト

• Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
  制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。 アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
  論文  参考訳（メタデータ） (2024-05-08T16:39:59Z)
• Fast algorithms for k-submodular maximization subject to a matroid constraint [10.270420338235237]
  マトロイド制約の下では、Threshold-Decreasing Algorithmを用いて$k$-submodular関数を最大化する。 我々は$k$-submodular関数に対して$(frac12 - epsilon)$-approximationアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-07-26T07:08:03Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
  マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。 本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。 マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-06-01T17:54:15Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• On the Complexity of Dynamic Submodular Maximization [15.406670088500087]
  濃度制約の下で$(0.5+epsilon)$-approximateを維持できるアルゴリズムは、任意の定数$epsilon>0$に対して、$mathitpolynomial$ in $n$というアモータイズされたクエリ複雑性を持つ必要がある。 これは、(0.5-epsilon)$-approximation with a $mathsfpolylog(n)$ amortized query complexityを達成している[LMNF+20, Mon20]の最近の動的アルゴリズムとは対照的である。
  論文  参考訳（メタデータ） (2021-11-05T00:04:29Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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