Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints

Shengminjie Chen, Yiwei Gao, Kaifeng Lin, Xiaoming Sun, Jialin Zhang

Abstract

Submodular maximization constitutes a prominent research topic in combinatorial optimization and theoretical computer science, with extensive applications across diverse domains. While substantial advancements have been achieved in approximation algorithms for submodular maximization, the majority of algorithms yielding high approximation guarantees are randomized. In this work, we investigate deterministic approximation algorithms for maximizing non-monotone submodular functions subject to matroid and knapsack constraints. For the two distinct constraint settings, we propose novel deterministic algorithms grounded in an extended multilinear extension framework. Under matroid constraints, our algorithm achieves an approximation ratio of $(0.385 - \epsilon)$, whereas for knapsack constraints, the proposed algorithm attains an approximation ratio of $(0.367 - \epsilon)$. Both algorithms run in $\mathrm{poly}(n)$ query complexity, where $n$ is the size of the ground set, and improve upon the state-of-the-art deterministic approximation ratios of $(0.367 - \epsilon)$ for matroid constraints and $0.25$ for knapsack constraints.

Introduction

Submodular functions are fundamental in modeling scenarios characterized by diminishing returns, where the marginal gain of adding an element decreases as the set grows. These functions are critical in fields such as viral marketing, sensor placement, and data summarization. However, many practical applications involve non-monotone functions—where adding elements can decrease total value—and are subject to structural constraints like matroids or budget constraints like knapsacks.

While randomized algorithms have historically provided the best approximation guarantees for these problems, they are often unsuitable for safety-critical systems or environments requiring strict reproducibility. Deterministic algorithms offer consistency but have previously struggled to match the performance of randomized approaches. This research aims to bridge this performance gap using a deterministic framework.

Methodology

The core of the proposed approach is the Extended Multilinear Extension (EME). Standard multilinear extensions facilitate continuous optimization of discrete functions but typically rely on random sampling for evaluation. EME circumvents this by maintaining a distribution with constant-size support, enabling exact, deterministic evaluation of the objective function.

Matroid Constraints

For matroid constraints, the authors introduce a hybrid approach. They first identify a "discrete stationary point" via local search. This point serves as a reference to guide a "continuous greedy" trajectory. By moving in directions orthogonal to this stationary point initially, the algorithm explores the solution space more effectively, avoiding suboptimal local optima.

Knapsack Constraints

Handling knapsack constraints is more challenging due to the lack of exchange properties found in matroids. The authors employ an enumeration strategy to identify "heavy" elements (those consuming a significant portion of the budget). For the remaining "lightweight" elements, they use density-based optimization. To ensure feasibility during the final discretization, the algorithm optimizes against a slightly reduced budget $(1-\epsilon)B$. A modified Pipage Rounding procedure is then used to convert the fractional solution into a discrete set.

Key Results

The proposed deterministic algorithms establish new state-of-the-art (SOTA) benchmarks for both constraint types. Notably, the approximation ratio for knapsack constraints improved from $0.25$ to $0.367 - \epsilon$, effectively matching the performance of many standard randomized algorithms.

Comparison of approximation ratios and query complexities for matroid and knapsack constraints.

As shown in the table above, the matroid algorithm achieves a ratio of $0.385 - \epsilon$ with $O_\epsilon(n^5)$ query complexity, while the knapsack algorithm reaches $0.367 - \epsilon$ with $O_\epsilon(n^{\epsilon^{-2}})$ complexity. These results significantly narrow the gap between deterministic and randomized performance guarantees.

Discussion and Future Work

This work demonstrates that deterministic algorithms can achieve competitive performance in non-monotone submodular maximization. However, a gap remains between the current $0.385$ ratio for matroids and the theoretical upper bound of $0.478$. Future research may focus on adapting the "aided" continuous greedy technique to knapsack constraints to further improve their ratios. Additionally, extending these deterministic methods to multi-dimensional constraints remains an open challenge for the field.

Summary updated

Abstract

Submodular maximization constitutes a prominent research topic in combinatorial optimization and theoretical computer science, with extensive applications across diverse domains. While substantial advancements have been achieved in approximation algorithms for submodular maximization, the majority of algorithms yielding high approximation guarantees are randomized. In this work, we investigate deterministic approximation algorithms for maximizing non-monotone submodular functions subject to matroid and knapsack constraints. For the two distinct constraint settings, we propose novel deterministic algorithms grounded in an extended multilinear extension framework. Under matroid constraints, our algorithm achieves an approximation ratio of $(0.385 - ε)$, whereas for knapsack constraints, the proposed algorithm attains an approximation ratio of $(0.367 -ε)$. Both algorithms run in $\mathrm{poly}(n)$ query complexity, where $n$ is the size of the ground set, and improve upon the state-of-the-art deterministic approximation ratios of $(0.367 - ε)$ for matroid constraints and $0.25$ for knapsack constraints.
BibTeX
@misc{chen2026deterministic,
  author = {Shengminjie Chen and Yiwei Gao and Kaifeng Lin and Xiaoming Sun and Jialin Zhang},
  title = {{Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints}},
  year = {2026},
  eprint = {2603.11996},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.11996},
}
Figure