Improved deterministic algorithms for non-monotone submodular maximization

DOI10.1007/978-3-031-22105-7_44arXiv2208.14388OpenAlexW4313343266MaRDI QIDQ6168972FDOQ6168972

Authors:

Publication date: 10 August 2023

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

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.

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)

Cites Work

• A threshold of ln n for approximating set cover
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• The budgeted maximum coverage problem
• An analysis of approximations for maximizing submodular set functions—I
• Fast algorithms for maximizing submodular functions
• Title not available (Why is that?)
• Maximizing submodular set functions subject to multiple linear constraints
• A note on maximizing a submodular set function subject to a knapsack constraint
• Optimal approximation for the submodular welfare problem in the value oracle model
• Submodular maximization by simulated annealing
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Deterministic Algorithms for Submodular Maximization Problems
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Submodular maximization with cardinality constraints
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Constrained submodular maximization via a nonsymmetric technique
• Improved deterministic algorithms for non-monotone submodular maximization

Cited In (6)

• Deterministic Algorithms for Submodular Maximization Problems
• Title not available (Why is that?)
• Sequence Independent Lifting for the Set of Submodular Maximization Problem
• 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
• Improved deterministic algorithms for non-monotone submodular maximization

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)