論文の概要: Deterministic Approximation for Submodular Maximization over a Matroid
in Nearly Linear Time
- arxiv url: http://arxiv.org/abs/2010.11420v1
- Date: Thu, 22 Oct 2020 03:52:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 08:29:31.464027
- Title: Deterministic Approximation for Submodular Maximization over a Matroid
in Nearly Linear Time
- Title（参考訳）: ほぼ直線時間におけるマトロイド上の部分モジュラー最大化の決定論的近似
- Authors: Kai Han, Zongmai Cao, Shuang Cui, Benwei Wu
- Abstract要約: マトロイド制約を受ける非単調で非負な部分モジュラ函数を最大化する問題について検討する。
この決定論的比は、$mathcalO(nr)$時間複雑さの下で$frac14$に改善できることを示す。
次に、TwinGreedyFastというより実用的なアルゴリズムを提案し、ほぼ直線的な実行時間で$frac14-epsilon$決定率を達成する。
- 参考スコア（独自算出の注目度）: 16.26380955876814
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of maximizing a non-monotone, non-negative submodular
function subject to a matroid constraint. The prior best-known deterministic
approximation ratio for this problem is $\frac{1}{4}-\epsilon$ under
$\mathcal{O}(({n^4}/{\epsilon})\log n)$ time complexity. We show that this
deterministic ratio can be improved to $\frac{1}{4}$ under $\mathcal{O}(nr)$
time complexity, and then present a more practical algorithm dubbed
TwinGreedyFast which achieves $\frac{1}{4}-\epsilon$ deterministic ratio in
nearly-linear running time of
$\mathcal{O}(\frac{n}{\epsilon}\log\frac{r}{\epsilon})$. Our approach is based
on a novel algorithmic framework of simultaneously constructing two candidate
solution sets through greedy search, which enables us to get improved
performance bounds by fully exploiting the properties of independence systems.
As a byproduct of this framework, we also show that TwinGreedyFast achieves
$\frac{1}{2p+2}-\epsilon$ deterministic ratio under a $p$-set system constraint
with the same time complexity. To showcase the practicality of our approach, we
empirically evaluated the performance of TwinGreedyFast on two network
applications, and observed that it outperforms the state-of-the-art
deterministic and randomized algorithms with efficient implementations for our
problem.
- Abstract（参考訳）: マトロイド制約を受ける非単調、非負のサブモジュラー関数を最大化する問題について検討する。
この問題の最もよく知られた決定論的近似比は、$\frac{1}{4}-\epsilon$ under $\mathcal{O}(({n^4}/{\epsilon})\log n)$ time complexityである。
この決定論的比を$\frac{1}{4}$ under $\mathcal{O}(nr)$ time complexity, そして、$\frac{1}{4}-\epsilon$ deterministic ratio in almost-linear running time of $\mathcal{O}(\frac{n}{\epsilon}\log\frac{r}{\epsilon})$とするより実用的なアルゴリズムTwinGreedyFastを示す。
提案手法は, 独立系の性質を十分に活用することで, 性能境界を向上できるような, 2つの候補解集合を同時に構築するアルゴリズムの枠組みに基づいている。
このフレームワークの副産物として、twingreedyfastが同じ時間複雑性を持つ$p$-setシステム制約の下で$\frac{1}{2p+2}-\epsilon$決定論的比を達成することも示します。
提案手法の実用性を実証するため,TwinGreedyFastを2つのネットワークアプリケーションで評価し,その性能が現状の決定性およびランダム化アルゴリズムより優れていることを示した。
関連論文リスト
- 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) - 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) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-17T15:27:33Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。