Arash Asadpour

  1. Maximizing Stochastic Monotone Submodular Functions.

    Authors: Arash Asadpour, Hamid Nazerzadeh, Amin Saberi
    Subjects: Optimization and Control
    Abstract

    We study the problem of maximizing a stochastic monotone submodular function
    with respect to a matroid constraint. We study the adaptivity gap - the ratio
    between the values of optimal adaptive and non-adaptive policies - and show
    that it is equal to e/(e-1). This result implies that the benefit of adaptivity
    is bounded. We also study the myopic policy and show that it is a
    1/2-approximation. Furthermore, when the matroid is uniform, approximation
    ratio of the myopic policy becomes 1-1/e which is optimum.

Syndicate content