mlsanityData to 13 Oct 2026

Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity

arXiv 2405.12252 ↗First posted 20 May 2024cs.DS cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

In this work, we consider the Submodular Maximization under Knapsack (SMK) constraint problem over the ground set of size n. The problem recently attracted a lot of attention due to its applications in various domains of combination optimization, artificial intelligence, and machine learning. We improve the approximation factor of the fastest deterministic algorithm from 6+ε to 5+ε while keeping the best query complexity of O(n), where ε >0 is a constant parameter. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions. Besides, by carefully analyzing the cost of candidate solutions, we obtain a tighter approximation factor.

Key facts. No citing papers in the map yet (data through 13 Oct 2026). Builds on 9 of its 29 references that are in the map. First posted on arXiv 20 May 2024.

Builds on

9 of 29 references.

References · 9

  1. 2020Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraintcited by 21
  2. 2016Constrained Submodular Maximization via a Non-symmetric Techniquecited by 17
  3. 2019"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsackcited by 14
  4. 2020Submodular Maximization in Clean Linear Timecited by 10
  5. 2021Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexitycited by 8
  6. 2023Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraintcited by 5
  7. 2017A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraintcited by 4
  8. 2022Improved Deterministic Algorithms for Non-monotone Submodular Maximizationcited by 4
  9. 2021Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Timecited by 2

Built on by

Not cited yet.