Online Dynamic Submodular Optimization

arXiv:2306.10835v3 Announce Type: replace-cross
Abstract: We propose new algorithms with provable performance for online binary optimization subject to general constraints and in dynamic settings. We consider the subset of problems in which the objective function is submodular. We propose the online submodular greedy algorithm (OSGA) which solves to optimality an approximation of the previous round loss function to avoid the NP-hardness of the original problem. We extend OSGA to a generic approximation function. We show that OSGA has a dynamic …

abstract algorithm algorithms approximation arxiv binary constraints cs.lg dynamic function general loss math.oc optimization performance type