SCIENCE@home

Streaming Submodular Maximization under a k-Set System Constraint

Ran Haba,Ehsan Kazemi,Moran Feldman,Amin Karbasi

Published 2020 in International Conference on Machine Learning

ABSTRACT

In this paper, we propose a novel framework that converts streaming algorithms for monotone submodular maximization into streaming algorithms for non-monotone submodular maximization. This reduction readily leads to the currently tightest deterministic approximation ratio for submodular maximization subject to a $k$-matchoid constraint. Moreover, we propose the first streaming algorithm for monotone submodular maximization subject to $k$-extendible and $k$-set system constraints. Together with our proposed reduction, we obtain $O(k\log k)$ and $O(k^2\log k)$ approximation ratio for submodular maximization subject to the above constraints, respectively. We extensively 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 summarization, and Twitter data summarization.

PUBLICATION RECORD

  • Publication year

    2020

  • Venue

    International Conference on Machine Learning

  • Publication date

    2020-02-09

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 2002.03352
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-47 of 47 references · Page 1 of 1

CITED BY

Showing 1-42 of 42 citing papers · Page 1 of 1