Date & Time: 

   2024 / 5 / 10  (Fri) 14:20 - 16:20

Location: 

   Delta Building R216, NTHU

Speaker: 

   高孟駿 教授

  國立陽明交通大學 資工系.

Topic: 

   Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost

Abstract: 

   We consider the hard-capacitated facility location problem with uniform facility cost (CFL-UFC). This problem arises as an indicator variation between the general CFL problem and the uncapacitated facility location (UFL) problem and is related to the profound capacitated k-median problem (CKM). In this work, we present a rounding-based 4-approximation algorithm for this problem, built on a two-staged rounding scheme that incorporates a set of novel ideas and also techniques developed in the past for both facility location and capacitated covering problems. Our result improves the decades-old LP-based ratio of 5 for this problem due to Levi et al. since 2004. We believe that the techniques developed in this work are of independent interests and may further lead to insights and implications for related problems.

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 under the guidance of Academician D.T. Lee on the design and analysis of approximation algorithms. I received my PhD degree and joined the IIS, Academia Sinica, as a postdoc in 2012. I joined the CSIE department in National Chung-Cheng University, Chiayi, Taiwan, in 2018 as an assistant professor. 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.