Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint

DOI10.1007/978-3-030-57602-8_18zbMath1485.90105OpenAlexW3047670293MaRDI QIDQ5918331

Min Cui, Da-Chuan Xu, Longkun Guo, Dan Wu

Publication date: 5 July 2021

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_18

zbMATH Keywords

parallel algorithmcardinality constraintnon-submodular optimizationsubmodularity ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10)

Related Items

A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions

Cites Work

• Unnamed Item
• Parametric monotone function maximization with matroid constraints
• Determinantal Point Processes for Machine Learning
• Maximizing Non-monotone Submodular Functions
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• Parallelizing greedy for submodular set function maximization in matroids and beyond
• Submodular maximization with matroid and packing constraints in parallel
• The adaptive complexity of maximizing a submodular function
• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Submodular Function Maximization in Parallel via the Multilinear Relaxation
• Maximize a monotone function with a generic submodularity ratio