2019/06/30 by Omid Sadeghi, Sadeghi, Omid, Reza Eghbali +3
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1907.00312
openalex publication_date 2019/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.