Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity

DOI10.1007/s10957-023-02353-7OpenAlexW4389884064MaRDI QIDQ6142066

Jiazhu Fang, Suning Gong, Ding-Zhu Du, Qingqin Nong

Publication date: 25 January 2024

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10957-023-02353-7

zbMATH Keywords

cardinality constraintDR-submodular maximizationdesign and analysis of approximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on maximizing a submodular set function subject to a knapsack constraint
• Maximizing monotone submodular functions over the integer lattice
• A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
• Maximizing Non-monotone Submodular Functions
• Optimal Value of Information in Graphical Models
• Rounds in Communication Complexity Revisited
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Settling the Query Complexity of Non-adaptive Junta Testing
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• 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
• Parallel algorithms for select and partition with noisy comparisons
• Fast algorithms for maximizing submodular functions
• On the Power of Adaptivity in Sparse Recovery
• Online submodular welfare maximization: Greedy is optimal

This page was built for publication: Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity