Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
Tan D. Tran, Canh V. Pham
This work studies the non-monotone DR-submodular Maximization over a ground set of subject to a size constraint . We propose two approximation algorithms for solving this pr…
cs.DS2025
Fast Stochastic Greedy Algorithm for -Submodular Cover Problem
Hue T. Nguyen, Tan D. Tran, Nguyen Long Giang +1
We study the -Submodular Cover () problem, a natural generalization of the classical Submodular Cover problem that arises in artificial intelligence and combinatorial optim…
cs.DS2024
Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
Canh V. Pham
In this work, we consider the Submodular Maximization under Knapsack (SMK) constraint problem over the ground set of size . The problem recently attracted a lot of attention due…