論文の概要: 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つのネットワークアプリケーションで評価し,その性能が現状の決定性およびランダム化アルゴリズムより優れていることを示した。
関連論文リスト
- Replicable Learning of Large-Margin Halfspaces [50.330457600322084]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳(メタデータ) (2024-02-21T15:06:51Z) - 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) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。