WorksComputer Science
Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse
Abstract
We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every , we give an algorithm with recourse whose reported set has, at every time, expected value at least times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above , even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above requires recourse that grows as a positive power of the cardinality budget. Thus is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was . Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.