Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover

Blake Harris, Viswanath Nagarajan
5/23/2024
cs.DScs.AIcs.LG

No confident code implementation found for this paper.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Partial-Monotone Adaptive Submodular Maximization

85% match2022

The Cost of Consistency: Submodular Maximization with Constant Recourse

81% match2024

Fairness in Monotone k-submodular Maximization: Algorithms and Applications

79% match2024

Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies

79% match2024

Practical Parallel Algorithms for Non-Monotone Submodular Maximization

79% match2023

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization

78% match2024

Cite this paper

@article{harris2024lower,
  title  = {Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover},
  author = {Blake Harris and Viswanath Nagarajan},
  year   = {2024},
  eprint = {2405.14995},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2405.14995v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2405.14995.svg)](https://codeofpaper.com/paper/2405.14995)

Discussion