Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint

Zihui Liu; Zhijie Zhang

In the authors' words

Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining. Motivated by large-scale applications where query efficiency is paramount, we study non-monotone SMK and focus on deterministic algorithms with linear query complexity. Prior deterministic linear-query algorithms achieve at best a $1/5 - ε$ approximation, falling short of the $1/4 - ε$ ratio attainable by randomized algorithms. We close this gap by presenting a deterministic $(1/4 - ε)$ -approximation with $O (n lo g^{2} (1/ ε) / ε^{2})$ queries. Our approach partitions the analysis based on the cost of the largest optimal element $r$ : when the cost of $r$ is moderate, we refine the threshold-twin-greedy framework via residual-budget enumeration to tighten the analysis; when the cost of $r$ is large, we reduce the problem to bicriteria submodular maximization. As a secondary contribution, we obtain a $(1/2 - ε, O (1/ ε))$ -bicriteria approximation with $O (n lo g (1/ ε) / ε^{2})$ queries, improving over the previous $O (n^{2} / ε)$ query bound.

Main resultThe abstract does not state a limitation.

Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint

In the authors' words

More on Algorithms & complexity that day

4-Block Integer Programming is in FPT

Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties

An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

Analysis of trade-offs in urban heat mitigation using a Bayesian Optimization framework for an urban canopy layer model

Factorisability of Low Dimensional Non-Negative Integer Matrices