# Metadata

- Title: Fast Approximation Algorithm for Non-monotone DR-submodular Maximization under Size Constraint
- Authors: Tan D. Tran, Canh V. Pham
- Year: 2026
- Venue: Journal of Combinatorial Optimization
- Primary group: dr-submodular
- Secondary tags: non-monotone, size-constraint, integer-lattice, deterministic, reduction-inspired
- Problem: non-monotone DR-submodular maximization on the integer lattice under a size constraint
- Main guarantee: introduces FastDrSub with approximation ratio about 0.044 in O(n log k) queries and FastDrSub+ with approximation ratio 1/4 - epsilon in O((n/epsilon) log(1/epsilon) log k) queries, emphasizing deterministic near-linear-time guarantees
- Key techniques: partitioning the lattice domain into two subspaces, deterministic thresholding, using a coarse constant-factor routine to guess the optimum for a plus-version algorithm
- Status: processed-deep
- Tags: #dr-submodular #non-monotone #integer-lattice #size-constraint #deterministic
- Inbox source: inbox/6. DrSubmodular.pdf