Can I read Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model on EtoBox?

Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model by Huang, Chien-Chung; Kakimura, Naonori; Mauras, Simon; Yoshida, Yuichi is a scholarly article available to read on EtoBox.

What is Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model about?

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is much gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat $1-\frac{1}{e}$ in the single-pass streaming model. Let $n$ be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio $\frac{2}{2+\sqrt{2}}+\varepsilon$ requires $\Omega\left(\frac{n}{K^2}\right)$ space for any $\varepsilon>0$, where $K$ is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio $\frac{K}{2K-1}+\varepsilon$ requires $\Omega\left(\frac{n}{K}\right)$ space for any $\varepsilon>0$, where $K$ is the rank of the given matroid. In addition, we give streaming algorithms when we only ha

Author

Huang, Chien-Chung; Kakimura, Naonori; Mauras, Simon; Yoshida, Yuichi

Published

2020

Language

EN