File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Appears in Collections:
Conference Paper: Deep Reinforcement Learning for Solving Directed Steiner Tree Problems
Title | Deep Reinforcement Learning for Solving Directed Steiner Tree Problems |
---|---|
Authors | |
Issue Date | 2022 |
Publisher | IEEE. |
Citation | TENCON 2022 - 2022 IEEE Region 10th International Conference (TENCON), 1-4 November 2022. In 2022 IEEE TENCON: Proceedings of 2022 IEEE Regional 10 International Confernece cum IEEE Hong Kong 50th Anniversary Celebration, November 1-4 2022, p. 1-5 How to Cite? |
Abstract | The design of approximation algorithms for solving NP-hard Combinatorial Optimization (CO) problems is usually challenging. In recent years, deep learning has demonstrated the power to solve specific CO problems, such as Travelling Salesman problem and Minimum Vertex Cover problem. In this paper, we propose a deep reinforcement learning approach based on graph neural networks (GNN) to tackle Directed Steiner Tree (DST) problem. Simulations are conducted to evaluate the proposed approach compared to benchmarks upon approximation ratios and execution time respectively. The results reveal the potential of our approach in solving DST problems in practice and the scalability that can be smoothly applied to disparate graphs after enough off-line training. |
Description | Theme: Tech-Biz Intelligence T1 Session 5: Machine Learning (3), Paper presentations |
Persistent Identifier | http://hdl.handle.net/10722/324329 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Yen, BP | - |
dc.contributor.author | Luo, Y | - |
dc.date.accessioned | 2023-01-20T06:38:42Z | - |
dc.date.available | 2023-01-20T06:38:42Z | - |
dc.date.issued | 2022 | - |
dc.identifier.citation | TENCON 2022 - 2022 IEEE Region 10th International Conference (TENCON), 1-4 November 2022. In 2022 IEEE TENCON: Proceedings of 2022 IEEE Regional 10 International Confernece cum IEEE Hong Kong 50th Anniversary Celebration, November 1-4 2022, p. 1-5 | - |
dc.identifier.uri | http://hdl.handle.net/10722/324329 | - |
dc.description | Theme: Tech-Biz Intelligence | - |
dc.description | T1 Session 5: Machine Learning (3), Paper presentations | - |
dc.description.abstract | The design of approximation algorithms for solving NP-hard Combinatorial Optimization (CO) problems is usually challenging. In recent years, deep learning has demonstrated the power to solve specific CO problems, such as Travelling Salesman problem and Minimum Vertex Cover problem. In this paper, we propose a deep reinforcement learning approach based on graph neural networks (GNN) to tackle Directed Steiner Tree (DST) problem. Simulations are conducted to evaluate the proposed approach compared to benchmarks upon approximation ratios and execution time respectively. The results reveal the potential of our approach in solving DST problems in practice and the scalability that can be smoothly applied to disparate graphs after enough off-line training. | - |
dc.language | eng | - |
dc.publisher | IEEE. | - |
dc.relation.ispartof | 2022 IEEE TENCON: Proceedings of 2022 IEEE Regional 10 International Confernece cum IEEE Hong Kong 50th Anniversary Celebration, November 1-4 2022 | - |
dc.rights | 2022 IEEE TENCON: Proceedings of 2022 IEEE Regional 10 International Confernece cum IEEE Hong Kong 50th Anniversary Celebration, November 1-4 2022. Copyright © IEEE. | - |
dc.title | Deep Reinforcement Learning for Solving Directed Steiner Tree Problems | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Yen, BP: benyen@business.hku.hk | - |
dc.identifier.authority | Yen, BP=rp01121 | - |
dc.identifier.doi | 10.1109/TENCON55691.2022.9977539 | - |
dc.identifier.hkuros | 343392 | - |
dc.identifier.spage | 1 | - |
dc.identifier.epage | 5 | - |
dc.publisher.place | Hong Kong, China | - |