Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
We show that the greedy algorithm for adaptive-submodular cover has approximation ratio at least 1.3*(1+ln Q). Moreover, the instance demonstrating this gap has Q=1. So, it invalidates a prior result in the paper ``Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization'' by Golovin-Krause, that claimed a (1+ln Q)^2 approximation ratio for the same algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningStochastic OptimizationSimilar Papers 제목 키워드 기반
Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide variety of adaptive stochastic optimizati…
Decision Makingfeature selectionSequential Decision MakingStochastic OptimizationStream Clipper: Scalable Submodular Maximization on Stream
We propose a streaming submodular maximization algorithm "stream clipper" that performs as well as the offline greedy algorithm on document/video summarization in practice. It adds elements from a stream either to a solu…
Video SummarizationPartial-Monotone Adaptive Submodular Maximization
Many sequential decision making problems, including pool-based active learning and adaptive viral marketing, can be formulated as an adaptive submodular maximization problem. Most of existing studies on adaptive submodul…
Active LearningDecision MakingMarketingSequential Decision MakingBeyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time
In this paper, we study the non-monotone adaptive submodular maximization problem subject to a cardinality constraint. We first revisit the adaptive random greedy algorithm proposed in \citep{gotovos2015non}, where they …
On the entropy numbers of the mixed smoothness function classes
Behavior of the entropy numbers of classes of multivariate functions with mixed smoothness is studied here. This problem has a long history and some fundamental problems in the area are still open. The main goal of this …