Tan D. Tran

activity

20232025

most citedLinear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint

1 citations · 1 across the 4 of their papers we have counts for

collaborators

5 papers

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 $n$ subject to a size constraint $k$ . We propose two approximation algorithms for solving this pr…

cs.DS2025

Fast Stochastic Greedy Algorithm for $k$ -Submodular Cover Problem

Hue T. Nguyen, Tan D. Tran, Nguyen Long Giang +1

We study the $k$ -Submodular Cover ( $k S C$ ) problem, a natural generalization of the classical Submodular Cover problem that arises in artificial intelligence and combinatorial optim…

cs.AI2024

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 $n$ . Our algorithm impro…

cs.DS2023

Robust Approximation Algorithms for Non-monotone $k$ -Submodular Maximization under a Knapsack Constraint

Dung T. K. Ha, Canh V. Pham, Tan D. Tran +1

The problem of non-monotone $k$ -submodular maximization under a knapsack constraint ($\kSMK$) over the ground set size $n$ has been raised in many applications in machine learning,…

cs.DS2023★ 1 cited

Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint

Canh V. Pham, Tan D. Tran, Dung T. K. Ha +1

This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of si…