Improved deterministic algorithms for non-monotone submodular maximization

DOI10.1016/j.tcs.2023.114293MaRDI QIDQ6140348

No author found.

Publication date: 2 January 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

deterministic algorithmsderandomizationmultiplicative updatessubmodular maximizationtwin greedy

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Efficient Submodular Function Maximization under Linear Packing Constraints
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Deterministic Algorithms for Submodular Maximization Problems
• Constrained Submodular Maximization via a Nonsymmetric Technique
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Submodular Maximization with Cardinality Constraints
• Fast algorithms for maximizing submodular functions
• A Unified Continuous Greedy Algorithm for Submodular Maximization

This page was built for publication: Improved deterministic algorithms for non-monotone submodular maximization