Online submodular maximization with preemption

摘要: Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role disciplines. We study natural online variant of this which elements arrive one-by-one the algorithm to maintain solution obeying certain at all times. Upon arrival an element, decide whether accept element into its may preempt previously chosen elements. goal is maximize submodular over set solution.We two special cases general derive upper lower bounds on competitive ratio. Specifically, we design 1/e-competitive for unconstrained case hold any subset elements, constant ratio algorithms where most k solution.