4 papers
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…
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…
Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint
Tan D. Tran, Canh V. Pham, Dung T. K. Ha +1
This work proposes an efficient parallel algorithm for non-monotone submodular maximization under a knapsack constraint problem over the ground set of size . Our algorithm impro…
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…