高孟駿 ( Mong-Jen Kao )

Associate Professor,
Hsinchu City, Taiwan.

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

x

My Research

My research focuses on the approximability of fundamental combinatorial optimization problems. This includes cover, packing, matching, flow, and cut problems along with their natural extensions. The general goal of fundamental research of this kind is not only to pin down the exact approximability of these problems but, more importantly, also to derive new algorithmic design & analysis techniques for problems with similar tastes.

Recruiting Message

I am recruiting highly motivated students who are interested in algorithm / theory related concepts in CS.
MS students who are willing to work hard on theory problems and conduct research spontaneously are welcome.
Feel free to contact me via email if fit.

For Students @ NYCU

陽明交大的同學大家好，我是系上的新老師高孟駿。
我的研究專長，主要是在基礎組合最佳化問題的近似演算法設計分析、以及可近似困難度的研究上面。
各個領域實務上會碰到的最佳化問題，絕大多數在計算上都是困難的 (NP-hard)，
亦即，在 P ≠ NP 及 指數時間猜想 (Exponential-Time Hypothesis) 等目前被廣泛接受的計算困難度猜想之下，
這些問題不存在有效率的演算方法。
在此前提下，對於這些既重要又困難的問題，我們能做的，是計算求取這些問題的「近似最佳解」(near-optimal solutions)。
由此自然衍生而出的問題，例如，如何設計與分析近似演算法、能夠有效率逼近最佳解到多好的程度、在計算上有多困難等，
都是有趣且極具挑戰的問題。
近似演算法領域的研究主軸，是探討各種類型的基礎 NP-hard 問題的近似演算法設計分析、以及可近似的困難度。
透過在這些具有代表性的基礎問題的演算法研究，一方面我們可以為實務上具有類似性質的問題帶來更好的解答，
在另一方面，透過這個過程，我們同時也檢視、探討更基礎的計算理論領域裡，相關的重要定理與猜想。
除了近似演算法之外，我也對各類型的演算法與理論議題有高度興趣。
我並不擅長上課(我的課上得不好)，但是對於理論研究，我有很高的熱忱與研究動能，想要做最好的研究。
我正在招募對理論研究有興趣的 專題生 / 碩博班學生，
若你對理論相關的題材，有高度的熱忱、也想試著專注做深入的研究的話，很歡迎找我聊聊。
理論的研究，往往需要長時間的構思以及深入的推導，實際上並不容易。
然而，做為國內頂尖大學的學生，我相信這是各位能力所及的事情。
若你對理論研究感興趣，同時不排斥在求學階段接觸較深入的演算法/理論議題的話，歡迎 email 與我聯絡。

x

Research Interests & Expertises

Special Honor / Awards

Work Experience

Education

Autobiography

I received my B.S. degree and M.S. degree in CS, National Taiwan University, in 2006 and 2008. I started my Ph.D study 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 energy-efficient 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 and worked for an extended stay period of 6 years just to concentrate more on my research. During the time, I was very fortunate to have Dr. Kai-Min Chung as a collaborator and a friend for rewarding discussion and comments for 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 fundamental combinatorial optimization problems. This includes cover problems, location problems, scheduling problems, etc, along with their natural extensions.

I enjoy the intriguing exploration process for unknowns that are fundamental in computer science.

Funded Projects

Past Projects:
x

Selected Publications

  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",
    To appear in the 34th International Symposium on Algorithms and Computation (ISAAC 2023), 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",
    To appear in the 34th International Symposium on Algorithms and Computation (ISAAC 2023), Kyoto, Japan.

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), Vancouver, Canada.

  2. Mong-Jen Kao,
    "A 4-approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost",
    To appear in the 34th International Symposium on Algorithms and Computation (ISAAC 2023), 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",
    To appear in the 34th International Symposium on Algorithms and Computation (ISAAC 2023), 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.

Extended Abstracts in Workshops

Domestic Workshops & Conferences

Technical Reports

Thesis & Dissertation

x

Forthcoming

Past

x

Members

MS Students

BS Students

Activity & Excursion

2023-09-06 攀岩體驗

2023-09-10 峨眉湖踏青

Alumni