高孟駿 ( 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
Quantum Computing,
Cryptography and Security

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.

For Students @ NYCU

陽明交大的同學大家好，我是系上的新老師老師高孟駿。
我的研究專長，主要是在基礎組合最佳化問題的近似演算法設計分析、以及可近似困難度的研究上面。
大多數實務上碰到的最佳化問題，在計算上都是困難的 (NP-hard)，
亦即，在 P ≠ NP 及 指數時間猜想 等目前被廣泛接受的計算困難度猜想之下，
這些問題不存在有效率的演算方法。
在此前提下，我們能做的，是計算這些問題的「近似最佳解」(near-optimal solutions)。
由此衍生而出的問題，例如，如何設計與分析演算法、能夠有效率逼近最佳解到多好的程度、在計算上有多困難等，
都是有趣且深具挑戰的問題。
近似演算法領域的研究主軸，是探討各類型基礎最佳化問題的近似演算法設計分析、以及其可近似的困難度。
透過研究這些具有代表性的基礎問題，一方面我們可以為實務上具有類似性質的問題帶來更好的解答，
在另一方面，透過這個過程，我們也同時檢視、探討更基礎的計算理論領域裡，相關的重要定理與猜想。
我正在招募對理論研究有興趣的 專題生 / 碩博班學生，
若你對理論相關的題材，有高度的熱忱、也想試著專注做深入的研究的話，很歡迎找我聊聊。(2021-09) (2024-02)

x

Research Interests & Expertises

Special Honor / Awards

Work Experience

Education

Autobiography

I received my B.S. degree and M.S. degree in the department of CSIE, National Taiwan University, in 2006 and 2008. I started my Ph.D study and was fortunate to work under the guidance of Academician D.T. Lee on the design and analysis of approximation algorithms. I visited KIT, Germany, in 2009 for a research training stay of two years and worked under the guidance of Prof. Dr. Dorothea Wagner. During the time, I was fortunate to have Prof. Dr. Jian-Jia Chen as a collaborator on scheduling problems. I finished my Ph.D degree in 2012 with dissertation ''An Algorithmic Approach to Local and Global Resource Allocations.''

I joined the IIS, Academia Sinica, in 2012 as a postdoc for an extended period of 6 years to concentrate on my research. During the time, I was fortunate to have Dr. Kai-Min Chung as a collaborator and a friend for discussions on my research and career. I joined the CSIE department in National Chung-Cheng University, Chiayi, Taiwan, in 2018 as an assistant professor and initiated my training as a faculty member in academic institutes.

In August 2021, I joined the CS department in National Yang-Ming Chiao-Tung University, Hsinchu, Taiwan, where I am serving my duty as an associate professor.

My research interests have been surrounding the design and analysis of approximation algorithms for various types of fundamental combinatorial optimization problems. I enjoy the intriguing exploration process for unknowns that are fundamental in computer science.

Funded Projects

Past Projects:
x

Selected Papers

  1. 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.

  2. 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. Mong-Jen Kao,
    "A 4-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.

  2. 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.

  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",
    To appear in the IEEE International Conference on Computer Communications (INFOCOM 2024), May 20-23, 2024, Vancouver, Canada.

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. 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",
    To appear in the IEEE International Conference on Computer Communications (INFOCOM 2024), May 20-23, Vancouver, Canada.

  2. Mong-Jen Kao,
    "A 4-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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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])

  8. 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])

  9. 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])

  10. 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])

  11. 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])

  12. 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.

  13. 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.

  14. 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.

  15. 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)

  16. 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

Forthcoming

Current

Past

x

2024-06-13 期末聚餐 & 導生聚

Members

MS Students

BS Students & PT-RAs

Activity & Excursion

2024-06-13 期末聚餐 & 導生聚

2024-02-26 飛鳯山健行

2024-01-09 期末聚餐

2023-09-10 峨眉湖踏青

2023-09-06 攀岩體驗

Alumni