Improved deterministic algorithms for non-monotone submodular maximization

DOI10.1007/978-3-031-22105-7_44MaRDI QIDQ6168972OpenAlexFDO

Authors

Publication date 10 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.14388

zbMATH Keywords

deterministic algorithmsknapsack constraintsubmodular maximizationmatroid constraint

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Abstract: Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic $0.283-o(1)$ approximation algorithm, while the previous best deterministic algorithm only achieves a $1/4$ approximation ratio. For the knapsack constraint, we provide a deterministic $1/4$ approximation algorithm, while the previous best deterministic algorithm only achieves a $1/6$ approximation ratio. For the linear packing constraints with large widths, we provide a deterministic $1/6-epsilon$ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints.

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 5485514 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• A note on maximizing a submodular set function subject to a knapsack constraint
• 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
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Constrained submodular maximization via a nonsymmetric technique
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Deterministic Algorithms for Submodular Maximization Problems
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Fast algorithms for maximizing submodular functions
• Improved deterministic algorithms for non-monotone submodular maximization
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Maximizing submodular set functions subject to multiple linear constraints
• Optimal approximation for the submodular welfare problem in the value oracle model
• Submodular maximization by simulated annealing
• Submodular maximization with cardinality constraints
• The budgeted maximum coverage problem

Cited in

(6)

• Sequence Independent Lifting for the Set of Submodular Maximization Problem
• Deterministic Algorithms for Submodular Maximization Problems
• scientific article; zbMATH DE number 7255156 (Why is no real title available?)
• Improved deterministic algorithms for non-monotone submodular maximization
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168972)