論文の概要: Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint
- arxiv url: http://arxiv.org/abs/2305.10292v2
- Date: Mon, 10 Jul 2023 10:40:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 22:08:23.526460
- Title: Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint
- Title(参考訳): Knapsack制約下での非単調部分モジュラ最大化に対する線形クエリ近似アルゴリズム
- Authors: Canh V. Pham, Tan D. Tran, Dung T.K. Ha, My T. Thai
- Abstract要約: この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
- 参考スコア(独自算出の注目度): 16.02833173359407
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work, for the first time, introduces two constant factor approximation
algorithms with linear query complexity for non-monotone submodular
maximization over a ground set of size $n$ subject to a knapsack constraint,
$\mathsf{DLA}$ and $\mathsf{RLA}$. $\mathsf{DLA}$ is a deterministic algorithm
that provides an approximation factor of $6+\epsilon$ while $\mathsf{RLA}$ is a
randomized algorithm with an approximation factor of $4+\epsilon$. Both run in
$O(n \log(1/\epsilon)/\epsilon)$ query complexity. The key idea to obtain a
constant approximation ratio with linear query lies in: (1) dividing the ground
set into two appropriate subsets to find the near-optimal solution over these
subsets with linear queries, and (2) combining a threshold greedy with
properties of two disjoint sets or a random selection process to improve
solution quality. In addition to the theoretical analysis, we have evaluated
our proposed solutions with three applications: Revenue Maximization, Image
Summarization, and Maximum Weighted Cut, showing that our algorithms not only
return comparative results to state-of-the-art algorithms but also require
significantly fewer queries.
- Abstract(参考訳): この研究は、初めて2つの定数因子近似アルゴリズムを導入し、非単調部分モジュラー最大化に対する線形クエリの複雑さを、クナップサック制約に従えば$n$、$\mathsf{dla}$および$\mathsf{rla}$という基底集合に対して導入した。
$\mathsf{DLA}$は6+\epsilon$の近似係数を提供する決定論的アルゴリズムであり、$\mathsf{RLA}$は4+\epsilon$の近似係数を持つランダム化アルゴリズムである。
どちらも$O(n \log(1/\epsilon)/\epsilon)$クエリの複雑さで実行される。
1) 基底集合を2つの適切な部分集合に分割することで、これらの部分集合上の最適に近い解を線形なクエリで見つけること、(2) しきい値のグリーディと2つの不一致集合の性質を組み合わせること、または解の品質を改善するためにランダムな選択プロセスである。
理論的解析に加えて,提案手法を収益最大化,画像要約,最大重み付きカットの3つのアプリケーションを用いて評価し,我々のアルゴリズムが比較結果を最先端のアルゴリズムに返却するだけでなく,クエリを著しく少なくすることを示した。
関連論文リスト
- Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳(メタデータ) (2023-09-21T12:42:52Z) - 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) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Parallel Quasi-concave set optimization: A new frontier that scales
without needing submodularity [14.93584434176082]
擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。
我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
論文 参考訳(メタデータ) (2021-08-19T15:50:41Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳(メタデータ) (2020-09-03T22:43:55Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳(メタデータ) (2020-08-12T15:40:21Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳(メタデータ) (2020-07-08T15:54:28Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳(メタデータ) (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。