---
title: "Efficient Parallel Algorithms with Linear Queries for Non-Monotone Submodular Maximization"
authors:
  - "Canh V. Pham"
  - "Tan D. Tran"
  - "Dung T. K. Ha"
  - "My T. Thai"
doi: "10.24963/ijcai.2026/259"
url: "https://ijcai.org/proceedings/2026/259"
pdf: "https://ijcai.org/proceedings/2026/0259.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "2328-2336"
track: "Main Track"
keywords:
  - "Constraint Satisfaction and Optimization: Constraint optimization problems"
  - "Machine Learning: Optimization"
  - "Constraint Satisfaction and Optimization: Constraint satisfaction"
  - "Machine Learning: Theory of deep learning"
---

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

Canh V. Pham, Tan D. Tran, Dung T. K. Ha, My T. Thai

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 2328-2336. DOI: [10.24963/ijcai.2026/259](https://doi.org/10.24963/ijcai.2026/259)

## Abstract

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 algorithms that attain the best
known adaptive complexity of O(log n), our approach preserves this adaptivity
while reducing the query complexity from O(n log k) to O(n) and improving
the approximation ratio from 0.172-epsilon to 0.193-epsilon.
Our algorithms are built upon LinAdapt, which achieves a constant
approximation ratio with O(log n) adaptive rounds and linear query
complexity by requiring only O(1) candidate guesses of the optimal value.
We further introduce the BoostAdapt algorithm, which improves the
approximation guarantee to 0.25-\epsilon with O(log n log k) adaptive
complexity and O(n log k) query complexity, based on a novel staggered greedy
threshold framework that alternately constructs two disjoint solution sets over
O(log k) sequential rounds. Extensive experiments on standard benchmark
datasets demonstrate that our algorithms consistently outperform
state-of-the-art methods in terms of solution quality, query complexity, and running time.