論文の概要: Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint
- arxiv url: http://arxiv.org/abs/2305.10292v1
- Date: Wed, 17 May 2023 15:27:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-18 15:10:56.762604
- 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つのアプリケーションを用いて評価し,我々のアルゴリズムが比較結果を最先端のアルゴリズムに返却するだけでなく,クエリを著しく少なくすることを示した。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。
本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
論文 参考訳（メタデータ） (2024-05-20T02:24:58Z) - Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。
アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
論文 参考訳（メタデータ） (2024-05-08T16:39:59Z) - 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) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。