TTTan D. Tran
Tan D. Tran
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Tan D. Tran has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Canh V. Pham
ORLab, Faculty of Computer Science, Phenikaa University, Yen Nghia Ward, Ha Dong District, Hanoi 12116, Vietnam
1 shared publication - Canh V. Pham
Phenikaa University
1 shared publication - Dung P. Trung
Phenikaa University
1 shared publication - Dung T. K. Ha
Phenikaa University
1 shared publication - Huan X. Hoang
Faculty of Information Technology Halong University Quang Ninh Vietnam VNU University of Engineering and Technology Ha Noi Vietnam
1 shared publication - Nguyen Thi Uyen
Vinh University
1 shared publication
Latest Publications
- 29 February 2024
- Published by Springer Nature
- p. 222-233
Improved Streaming Algorithm for Minimum Cost Submodular Cover Problem
- 29 February 2024
- Published by Springer Nature
- p. 222-233
Improved Streaming Algorithm for Minimum Cost Submodular Cover Problem
- Open Access
Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint
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, such as data summarization, information propagation, etc. However, existing algorithms for the problem are facing questioning of how to overcome the non-monotone case and how to fast return a good solution in case of the big size of data. This paper introduces two deterministic approximation algorithms for the problem that competitively improve the query complexity of existing algorithms. Our first algorithm, $\LAA$, returns an approximation ratio of $1/19$ within $O(nk)$ query complexity. The second one, $\RLA$, improves the approximation ratio to $1/5-ε$ in $O(nk)$ queries, where $ε$ is an input parameter. Our algorithms are the first ones that provide constant approximation ratios within only $O(nk)$ query complexity for the non-monotone objective. They, therefore, need fewer the number of queries than state-of-the-the-art ones by a factor of $Ω(\log n)$. Besides the theoretical analysis, we have evaluated our proposed ones with several experiments in some instances: Influence Maximization and Sensor Placement for the problem. The results confirm that our algorithms ensure theoretical quality as the cutting-edge techniques and significantly reduce the number of queries.Open AccessRobust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint
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, such as data summarization, information propagation, etc. However, existing algorithms for the problem are facing questioning of how to overcome the non-monotone case and how to fast return a good solution in case of the big size of data. This paper introduces two deterministic approximation algorithms for the problem that competitively improve the query complexity of existing algorithms. Our first algorithm, $\LAA$, returns an approximation ratio of $1/19$ within $O(nk)$ query complexity. The second one, $\RLA$, improves the approximation ratio to $1/5-ε$ in $O(nk)$ queries, where $ε$ is an input parameter. Our algorithms are the first ones that provide constant approximation ratios within only $O(nk)$ query complexity for the non-monotone objective. They, therefore, need fewer the number of queries than state-of-the-the-art ones by a factor of $Ω(\log n)$. Besides the theoretical analysis, we have evaluated our proposed ones with several experiments in some instances: Influence Maximization and Sensor Placement for the problem. The results confirm that our algorithms ensure theoretical quality as the cutting-edge techniques and significantly reduce the number of queries.