Title: streaming submodular maximization under a k-system constraint

Authors: Haba, Ran and Kazemi, Ehsan and Feldman, Moran and Karbasi, Amin

Abstract

In this paper, we propose a novel framework that converts streaming algorithms for monotone submodular maximization into streaming algo- rithms for non-monotone submodular maximiza- tion. This reduction readily leads to the currently tightest deterministic approximation ratio for sub- modular maximization subject to a k-matchoid constraint. Moreover, we propose the first stream- ing algorithm for monotone submodular maxi- mization subject to k-extendible and k-set system constraints. Together with our proposed reduction, we obtain O(k log k) and O(k2 log k) approxima- tion ratio for submodular maximization subject to the above constraints, respectively. We exten- sively evaluate the empirical performance of our algorithm against the existing work in a series of experiments including finding the maximum independent set in randomly generated graphs, maximizing linear functions over social networks, movie recommendation, Yelp location summa- rization, and Twitter data summarization.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale