Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.25679 · 2 citations · 30 references
Computer Science

TL;DR

This work studies non-monotone SMK and focuses on deterministic algorithms with linear query complexity and obtains a deterministic submodular maximization approximation with bicriteria approximation with O(n\log(1/\varepsilon)/\varepsilon)/\varepsilon^2) queries, improving over the previous $O(n^2/\varepsilon)$ query bound.

Abstract

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-\varepsilon$ approximation, falling short of the $1/4-\varepsilon$ ratio attainable by randomized algorithms. We close this gap by presenting a deterministic $(1/4-\varepsilon)$-approximation with $O(n\log^2(1/\varepsilon)/\varepsilon^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-\varepsilon, O(1/\varepsilon))$-bicriteria approximation with $O(n\log(1/\varepsilon)/\varepsilon^2)$ queries, improving over the previous $O(n^2/\varepsilon)$ query bound.

View source

Similar papers

#machine learning Preprint Sep 2026

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

This work proves that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is 1-1/e-\varepsilon, and determines the exact curvature-dependent threshold $1-(\sqrt2-1)\vartheta$ for weighted coverage with weighted coverage with $O(\varepsilon^{-1})$ recourse.

Shi Fu, Qi-Xin Zhang, Da-Cheng Tao · 0 citations
Preprint Oct 2026

Quantum Submodular Maximization

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected...

Yong-Gang Jiang, Xiao-Ming Sun, Peng-Hui Yao et al. · 0 citations
Preprint Oct 2026

A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints

Submodular maximization arises in a wide range of combinatorial optimization problems and has been extensively studied from the perspective of approximation algorithms. For maximizing nonnegative, non-monotone submodular functions subject to a matroid constraint, randomized algorithms achieve a $0.401$-approximation, w...

Shengminjie Chen, Kai-Feng Lin, Xiao-Ming Sun et al. · 0 citations
Conference Open access Sep 2026

Efficient Parallel Algorithms with Linear Queries for Non-Monotone Submodular Maximization

In this work, we propose the first constant-approximation algorithms, LinAst and LinAtg, which simultaneously achieve optimal query complexity O(n) and adaptive complexity O(log n) for non-monotone submodular maximization under a cardinality constraint k over a ground set of size n. Specifically, compared with existing...

Canh V. Pham, Tan D. Tran, Dung T. K. Ha et al. · 0 citations
Preprint Oct 2026

Query Complexity of Densest Sub(hyper)graph Problems

Rubinstein et al. introduce the study of connectivity and minimum cut problems in the cut query model, where an algorithm can only access the edges of a graph through CUT queries. In this work, we examine the query complexity of densest subgraph problems. Our first contribution is to generalize the uniform sparsificati...

Sinan G. Aksoy, Eli M. Friedman, Nate Veldt et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.