高孟駿 ( Mong-Jen Kao )

Associate Professor,
Hsinchu City, Taiwan.

Office: EC445
Tel: 03-5712121 #56634
Email: mjkao-at-cs.nctu.edu.tw

x

Research Interests

Design and Analysis of Approximation Algorithms,
Computational Complexity Theory

Recruiting Message / 招募訊息

I am recruiting self-motivated PhD/MS/BS students for research works.
Students who are willing to work spontaneously on theory problems are welcome to contact me.

x

Autobiography

I am a professor in the Department of Computer Science, National Yang-Ming Chiao-Tung University (NYCU), starting from August 2025. Prior to joining NYCU in 2021, I was with the department of CSIE, National Chung-Cheng University, as an assistant professor and IIS, Academia Sinica, as a postdoc researcher. I received my Ph.D. from the department of CSIE, National Taiwan University, where I was very fortunate to work under the guidance of Academician D.T. Lee.

My research interests primarily surround the design and analysis of approximation algorithms for various combinatorial optimization problems. I enjoy the intriguing exploration process for unknowns that are important in computer science.

Honor / Awards

Education

Funded Research Projects

Past Projects:
x

Selected Papers

  1. Hyung-Chan An, Mong-Jen Kao, Changyeol Lee, and Mu-Ting Lee,
    "Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics".
    To appear in the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), Sydney, Australia.

  2. Mong-Jen Kao,
    "On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem".
    In proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'23), January 22-25, 2023, Florence, Italy.

  3. Mong-Jen Kao,
    "Iterative Partial Rounding for Vertex Cover with Hard Capacities".
    In procedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'17), January 16-19, 2017, Barcelona, Spain. ([arXiv])

Recent Works

  1. Shu-Wei Chang, Jian-Jhih Kuo, Mong-Jen Kao, Bo-Zhong Chen, and Qian-Jing Wang,
    "Near-Optimal UAV Deployment for Delay-Bounded Data Collection in IoT Networks",
    In the IEEE International Conference on Computer Communications (INFOCOM 2024), May 20-23, 2024, Vancouver, Canada.

  2. Hyung-Chan An and Mong-Jen Kao,
    "On the Connected Minimum Sum of Radii Problem",
    In proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024), December 8-11, Sydney, Australia.

Journal Articles

  1. Eunpyeong Hong and Mong-Jen Kao,
    "Approximation Algorithm for Vertex Cover with Multiple Covering Constraints". Algorithmica, 84: 1-12, 2022. DOI: 10.1007/s00453-021-00885-w

  2. Mong-Jen Kao,
    "Iterative Partial Rounding for Vertex Cover with Hard Capacities". Algorithmica, 83(1): 45-71, 2021. DOI: 10.1007/s00453-020-00749-9

  3. Mong-Jen Kao, Jia-Yau Shiau, Ching-Chi Lin, and D.T. Lee,
    "Tight Approximation for Partial Vertex Cover with Hard Capacities". Theoretical Computer Science, 778: 61-72, 2019. DOI: 10.1016/j.tcs.2019.01.027

  4. Mong-Jen Kao, Hai-Lun Tu, and D.T. Lee,
    "O(f) Bi-approximation for Capacitated Covering with Hard Capacities". Algorithmica, 81(5): 1800-1817, 2019. DOI: 10.1007/s00453-018-0506-6

  5. Bang-Sin Dai, Mong-Jen Kao, and D.T. Lee,
    "Optimal Time-convex Hull for a Straight-line Highway in Lp-metrics". Computational Geometry, volume 53, page 1-20, 2016.

  6. Mong-Jen Kao, Han-Lin Chen, and D.T. Lee,
    "Capacitated Domination: Problem Complexity and Approximation Algorithms". Algorithmica, 72(1): 1-43, 2015.

  7. Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner,
    "Online Dynamic Power Management with Hard Real-Time Guarantees". Theoretical Computer Science, volume 595, pages 46-64, 2015.

  8. Mong-Jen Kao, Bastian Katz, Marcus Krug, D.T. Lee, Ignaz Rutter, and Dorothea Wagner,
    "Density Maximization Problem in Graphs". Journal of Combinatorial Optimization, 26(4): 723-754, 2013.

  9. Mong-Jen Kao, Chung-Shou Liao, and D.T. Lee,
    "Capacitated Domination Problem". Algorithmica, 60:274-299, 2011.

International Conference Papers

  1. Hyung-Chan An, Mong-Jen Kao, Changyeol Lee, and Mu-Ting Lee,
    "Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics".
    To appear in the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), Sydney, Australia.

  2. Hyung-Chan An and Mong-Jen Kao,
    "On the Connected Minimum Sum of Radii Problem",
    In proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024), December 8-11, Sydney, Australia.

  3. Shu-Wei Chang, Jian-Jhih Kuo, Mong-Jen Kao, Bo-Zhong Chen, and Qian-Jing Wang,
    "Near-Optimal UAV Deployment for Delay-Bounded Data Collection in IoT Networks",
    In the IEEE International Conference on Computer Communications (INFOCOM 2024), May 20-23, Vancouver, Canada.

  4. Mong-Jen Kao,
    "Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost",
    In proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), December 3-6, Kyoto, Japan.

  5. Ting-Yo Kuo, Yu-Han Chen, Andrea Frosini, Sun-Yuan Hsieh, Shi-Chun Tsai, and Mong-Jen Kao,
    "On Min-Max Graph Balancing with Strict Negative Correlation Constraints",
    In proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), December 3-6, Kyoto, Japan.

  6. Mong-Jen Kao,
    "On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem".
    In proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'23), January 22-25, 2023, Florence, Italy.

  7. Eunpyeong Hong and Mong-Jen Kao,
    "Approximation Algorithm for Vertex Cover with Multiple Covering Constraints".
    In proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC'18), December 16-19, 2018, Yilan, Taiwan.

  8. Jia-Yau Shiau, Mong-Jen Kao, Ching-Chi Lin, and D.T. Lee,
    "Tight Approximation for Partial Vertex Cover with Hard Capacities".
    In proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC'17), December 09-12, 2017, Phuket, Thailand.

  9. Mong-Jen Kao,
    "Iterative Partial Rounding for Vertex Cover with Hard Capacities".
    In procedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'17), January 16-19, 2017, Barcelona, Spain. ([arXiv])

  10. Mong-Jen Kao, Hai-Lun Tu, and D.T. Lee, "O(f) Bi-approximation for Capacitated Covering with Hard Capacities". In proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC'16), December 12-14, 2016, Sydney, Australia. ([arXiv])

  11. Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner, "Online Dynamic Power Management with Hard Real-Time Guarantees". In proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS'14), March 5-8, 2014, Lyon, France. ([arXiv])

  12. Bang-Sin Dai, Mong-Jen Kao, and D.T. Lee, "Optimal Time-Convex Hull under the Lp Metrics". In proceedings of the 13rd Algorithms and Data Structures Symposium (WADS'13), August 12-14, London, Canada. ([arXiv])

  13. Mong-Jen Kao, Jian-Jia Chen, Ignaz Rutter, and Dorothea Wagner, "Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem". In proceedings of the 23rd International Symposium on Algorithms and Computatoin (ISAAC'12), December 19-21, Taipei, Taiwan. ([arXiv])

  14. Mong-Jen Kao and D.T. Lee, "Capacitated Domination: Constant Factor Approximations for Planar Graphs". In proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC'11), December 5-8, 2011, Yokohama, Japan.

  15. Mong-Jen Kao, Bastian Katz, Marcus Krug, D.T. Lee, Martin Nöllenburg, Ignaz Rutter, and Dorothea Wagner, "Connecting Two Trees with Optimal Routing Cost". In proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG'11), August 10-12, 2011, Toronto, Canada.

  16. Mong-Jen Kao, Bastian Katz, Marcus Krug, D.T. Lee, Ignaz Rutter, and Dorothea Wagner, "Density Maximization Problem in Graphs". In proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON'11), August 14-16, 2011, Dallas, US.

  17. Mong-Jen Kao and Han-Lin Chen, "Approximation Algorithms for the Capacitated Domination Problem". In proceedings of the 4th International Frontiers of Algorithmics Workshop (FAW'2010), August 11-13, 2010, Wuhan, China. (Best Student Paper Award)

  18. Mong-Jen Kao and Chung-Shou Liao, "Capacitated Domination Problem". In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC'2007), December 17-19, 2007, Sendai, Japan.

Other Works

Thesis & Dissertation

x

Current

Past

x

For Students @ NYCU

各位陽明交大的同學好,

我個人的研究主軸, 圍繞在各類型基礎組合最佳化問題的近似演算法設計分析、以及可近似困難度的研究上面。
過去曾在 Capacitated Covering / Location 等具挑戰性的問題上得到一系列的結果,
並在演算法領域頂尖國際會議 SODA 上發表數篇單一作者研究成果。

除此之外, 近年我也與實驗室的研究生/專題生探討基礎排程問題、路徑規劃問題、clustering、以及 distance embedding 問題等。
這些都是相當有趣、同時也具高度挑戰性的演算法研究問題。

我個人相信, 好的研究成果, 來自於天賦與努力兩者的結合.
因此, 我期望我實驗室的學生, 能夠持續努力且用心地面對本份內的研究工作, 並在碩班期間, 創造佳蹟, 累積未來的競爭力。

我的實驗室正在招募對演算法/理論研究有興趣以及熱忱的 專題生/碩博班學生，
若你對演算法/理論相關的題材，有高度的熱忱、也想試著專注做深入的研究、面對挑戰，歡迎與我聯絡。(2024-11-5)

Members

MS Students

BS Students & PT-RAs

Alumni (@NYCU)

Alumni