Competitive Algorithms for Online Budget-Constrained Continuous DR-Submodular Problems
arXiv:1907.00312
Abstract
In this paper, we study a certain class of online optimization problems, where the goal is to maximize a function that is not necessarily concave and satisfies the Diminishing Returns (DR) property under budget constraints. We analyze a primal-dual algorithm, called the Generalized Sequential algorithm, and we obtain the first bound on the competitive ratio of online monotone DR-submodular function maximization subject to linear packing constraints which matches the known tight bound in the special case of linear objective function.
arXiv commentSubmitted to NeurIPS 2019
References in corpus (6)
- Convergence Rate of Frank-Wolfe for Non-Convex Objectives
- Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
- Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
- Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
- Competitive Online Algorithms for Resource Allocation over the Positive Semidefinite Cone
- Worst Case Competitive Analysis of Online Algorithms for Conic Optimization