The submodularity of two-stage stochastic maximum-weight independent set problems.

In this paper, we extend the maximal independent set problem to two-stage stochastic case: given an independence system associated with one deterministic weight function and a random weight function, the goal is to find two nonoverlapping independent subsets from these two stages with the maximum total weight. In this paper, we study the submodularity of three kinds of two-stage independent set problems with max-weight. When the independent set problem is a matroid constraint, we can show its submodularity. However, neither submodular nor supermodular maximization problem can be obtained for the knapsack independent set problem by designing a counterexample. At last, we show that the robust two-stage stochastic maximum-weight uniform matroid problem can be formulated as a γ -submodular problem with cardinality constraint and also give a lower bound for γ. • The submodularity of two-stage stochastic matroid problem with maximum-weight is studied using properties of bases and the circuits in matroids. • An instance of two-stage stochastic knapsack problem which is not a submodular or supermodular maximization problem is proposed. • The robust two-stage stochastic max-weight problem with cardinality constraint can be formulated as a weakly submodular maximization problem. [ABSTRACT FROM AUTHOR]