Discrete stochastic submodular maximization: Adaptive vs. non-adaptive vs. offline

Lisa Hellerstein, Devorah Kletenik, Patrick Lin

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We consider the problem of stochastic monotone submodular function maximization, subject to constraints. We give results on adaptivity gaps, and on the gap between the optimal offline and online solutions. We present a procedure that transforms a decision tree (adaptive algorithm) into a non-adaptive chain. We prove that this chain achieves at least T times the utility of the decision tree, over a product distribution and binary state space, where T = mini,j Pr[xi = j]. This proves an adaptivity gap of 1/T (which is 2 in the case of a uniform distribution) for the problem of stochastic monotone submodular maximization subject to state-independent constraints. For a cardinality constraint, we prove that a simple adaptive greedy algorithm achieves an approximation factor of (1 – 1/eT) with respect to the optimal offline solution; previously, it has been proven that the algorithm achieves an approximation factor of (1 – 1/e) with respect to the optimal adaptive online solution. Finally, we show that there exists a non-adaptive solution for the stochastic max coverage problem that is within a factor (1− 1/e) of the optimal adaptive solution and within a factor of T (1 – 1/e) of the optimal offline solution.

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Complexity - 9th International Conference, CIAC 2015, Proceedings
    EditorsPeter Widmayer, Vangelis Th. Paschos
    PublisherSpringer Verlag
    Pages235-248
    Number of pages14
    ISBN (Print)9783319181721
    DOIs
    StatePublished - 2015
    Event9th International Conference on Algorithms and Complexity, CIAC 2015 - Paris, France
    Duration: May 20 2015May 22 2015

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume9079
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other9th International Conference on Algorithms and Complexity, CIAC 2015
    CountryFrance
    CityParis
    Period5/20/155/22/15

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Discrete stochastic submodular maximization: Adaptive vs. non-adaptive vs. offline'. Together they form a unique fingerprint.

    Cite this