高孟駿 ( 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.

To Prospective Students

I welcome highly motivated students who share with me interests in theoretical computer science (TCS) and general theory / algorithm related concepts.
MS students who are willing to work hard on theory problems and finish the assignments spontaneously are also welcome.
Contact me for further info if fit.

To Ambitious Top Prospects

For ambitious top prospects who wish to pursue in the future
  1. a higher academic degree, be it MS or Ph.D, abroad or domestic,
  2. a career path in the academics, or
  3. just theory research out of interests,
I invite you to challenge the top theory research problems and make high-quality research publications.
This is in general not an easy task to accomplish, but it will be an imperishable achievement that is worthy of the efforts.
Contact me directly for research in this case, as I am in general not great in lecturing.
Also check out my recent research papers for more concrete info.

x

Research Interests

Approximability Studies for Fundamental Combinatorial Optimization Problems

Professional Expertises

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

Recent Drafts

  1. Mong-Jen Kao,
    "Improved LP-based Approximation Algorithms for Facility Location with Hard Capacities", manuscript, 2020. [arXiv]
  2. (submitted to FOCS21, under review)

Journal Articles

  1. Eunpyeong Hong and Mong-Jen Kao,
    "Approximation Algorithm for Vertex Cover with Multiple Covering Constraints". Algorithmica, accepted with minor revision, to appear soon, 2020.
  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

  1. 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.
  2. 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.
  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])
  4. 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])
  5. 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])
  6. 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])
  7. 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])
  8. 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.
  9. 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.
  10. 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.
  11. 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)
  12. 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

Current

Past Courses