Dung T. K. Ha
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
Dung T. K. Ha has a total of 15 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
7 shared publications - Tan D. Tran
ORLab, Phenikaa School of Computing, Phenikaa University, Hanoi, Vietnam
3 shared publications - Anh T. N. Vu
Phenikaa University
1 shared publication - Canh V. Pham
Phenikaa University
1 shared publication - Chí Quang Vũ
Faculty of Information Security, People’s Security Academy, Hanoi, Vietnam
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
Latest Publications
- 12 August 2026
- Published by Springer Nature
- p. 194-208
Budgeted Object Detection via Online Submodular Approximation Algorithm
- 12 August 2026
- Published by Springer Nature
- p. 194-208
Budgeted Object Detection via Online Submodular Approximation Algorithm
- 15 July 2025
- Published by World Scientific Pub Co Pte Ltd in Asia-Pacific Journal of Operational Research
- Vol. 43 (04)
k-Submodular Maximization Under Individual Knapsack Constraints: Applications and Streaming Algorithm
The [ ]-submodular optimization problems have been an active research area with many applications in machine learning, such as data summarization, influence maximization, and maximum revenue. In this work, we investigate the problem of [ ]-submodular maximization under individual knapsack constraints ([ ]) that capture various realities of such applications. We solve the problem in a streaming setting that requires two passes over the data and a reasonable amount of memory. In particular, we propose a streaming algorithm named [ ][ ]which runs in [ ] query complexity, takes [ ] space complexity, and achieves an approximation ratio of [ ] for monotone objective function; [ ] for the non-monotone objective function, where [ ] is the size of the ground set, [ ] is the total budget and [ ] is an input parameter. We validate our algorithm in two applications of the studied problem, including revenue maximization and sensor placement on some benchmark datasets. The experimental results show that our streaming algorithm provides higher-quality solutions with lower query complexity than the existing baseline algorithm.
- 15 July 2025
- Published by World Scientific Pub Co Pte Ltd in Asia-Pacific Journal of Operational Research
- Vol. 43 (04)
k-Submodular Maximization Under Individual Knapsack Constraints: Applications and Streaming Algorithm
The [ ]-submodular optimization problems have been an active research area with many applications in machine learning, such as data summarization, influence maximization, and maximum revenue. In this work, we investigate the problem of [ ]-submodular maximization under individual knapsack constraints ([ ]) that capture various realities of such applications. We solve the problem in a streaming setting that requires two passes over the data and a reasonable amount of memory. In particular, we propose a streaming algorithm named [ ][ ]which runs in [ ] query complexity, takes [ ] space complexity, and achieves an approximation ratio of [ ] for monotone objective function; [ ] for the non-monotone objective function, where [ ] is the size of the ground set, [ ] is the total budget and [ ] is an input parameter. We validate our algorithm in two applications of the studied problem, including revenue maximization and sensor placement on some benchmark datasets. The experimental results show that our streaming algorithm provides higher-quality solutions with lower query complexity than the existing baseline algorithm.
- 13 March 2025
- Published by Springer Nature in Optimization Letters
- Vol. 19 (9) , 1929-1952
Practical algorithm for minimum cost submodular cover problem with performance guarantees
- 13 March 2025
- Published by Springer Nature in Optimization Letters
- Vol. 19 (9) , 1929-1952
Practical algorithm for minimum cost submodular cover problem with performance guarantees
- 1 June 2024
- Published by World Scientific Pub Co Pte Ltd in Asia-Pacific Journal of Operational Research
- Vol. 41 (06)
Efficient Parallel Algorithm for Minimum Cost Submodular Cover Problem with Lower Adaptive Complexity
In this paper, we study the Minimum Cost Submodular Cover ([ ]) problem over the ground set of size [ ], which aims at finding a subset with the minimal cost required so that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of operations research and artificial intelligence. However, the existing algorithms for this problem may not be easy to parallelize because of their costly adaptive complexity. However, the existing algorithms for this problem may not be effectively parallelized because of their costly adaptive complexity. This paper proposes an efficient parallel algorithm that returns a [ ]-bicriteria approximation solution within [ ] adaptive complexity, where [ ] are fixed parameters. Our algorithm requires [ ] query complexity, however, it can reduce to [ ] instead while retaining a low adaptive complexity of [ ]. Therefore, our algorithm not only achieves the same approximation guarantees as the state of the art but also significantly improves the best-known low adaptive complexity algorithm for the above problem.
- 1 June 2024
- Published by World Scientific Pub Co Pte Ltd in Asia-Pacific Journal of Operational Research
- Vol. 41 (06)
Efficient Parallel Algorithm for Minimum Cost Submodular Cover Problem with Lower Adaptive Complexity
In this paper, we study the Minimum Cost Submodular Cover ([ ]) problem over the ground set of size [ ], which aims at finding a subset with the minimal cost required so that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of operations research and artificial intelligence. However, the existing algorithms for this problem may not be easy to parallelize because of their costly adaptive complexity. However, the existing algorithms for this problem may not be effectively parallelized because of their costly adaptive complexity. This paper proposes an efficient parallel algorithm that returns a [ ]-bicriteria approximation solution within [ ] adaptive complexity, where [ ] are fixed parameters. Our algorithm requires [ ] query complexity, however, it can reduce to [ ] instead while retaining a low adaptive complexity of [ ]. Therefore, our algorithm not only achieves the same approximation guarantees as the state of the art but also significantly improves the best-known low adaptive complexity algorithm for the above problem.
- 29 February 2024
- Published by Springer Nature
- p. 186-197
Fast Bicriteria Approximation Algorithm for Minimum Cost Submodular Cover Problem
- 29 February 2024
- Published by Springer Nature
- p. 186-197
Fast Bicriteria Approximation Algorithm for Minimum Cost Submodular Cover Problem
- Open Access
- 7 December 2023
- Published by Association for Computing Machinery (ACM)
- p. 56-62
Maximizing a $k$-Submodular Maximization Function under an Individual Knapsack Constraint
In this work, we consider a novel problem of maximizing monotone k-submodular functions under the individual knapsack constraint () over the ground set V, which has been found numerous applications in machine learning, including data summarization and information propagation. We propose an approximation algorithm that has approximation ratio and takes O(nklog (n)/ϵ) query complexity, where ϵ is an input parameter. Alongside theoretical analysis, we conduct extensive experiments on our proposed algorithm via some applications, such as Influence Maximization and Sensor Placement. The experimental results demonstrate that our algorithm gives competitive solution quality with state-of-the-art techniques but significantly reduces the required queries.
- 7 December 2023
- Published by Association for Computing Machinery (ACM)
- p. 56-62
Open AccessMaximizing a $k$-Submodular Maximization Function under an Individual Knapsack Constraint
In this work, we consider a novel problem of maximizing monotone k-submodular functions under the individual knapsack constraint () over the ground set V, which has been found numerous applications in machine learning, including data summarization and information propagation. We propose an approximation algorithm that has approximation ratio and takes O(nklog (n)/ϵ) query complexity, where ϵ is an input parameter. Alongside theoretical analysis, we conduct extensive experiments on our proposed algorithm via some applications, such as Influence Maximization and Sensor Placement. The experimental results demonstrate that our algorithm gives competitive solution quality with state-of-the-art techniques but significantly reduces the required queries.
- 10 October 2023
- Published by Elsevier in Computers & Operations Research
- Vol. 161
Improved approximation algorithms for -submodular maximization under a knapsack constraint- 10 October 2023
- Published by Elsevier in Computers & Operations Research
- Vol. 161
Improved approximation algorithms for -submodular maximization under a knapsack constraint- 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. - 18 April 2022
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 44 (1) , 723-751
Maximizing k-submodular functions under budget constraint: applications and streaming algorithms
- 18 April 2022
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 44 (1) , 723-751
Maximizing k-submodular functions under budget constraint: applications and streaming algorithms