演講時間: 113年5月29日（三） 14:00~16:00

演講地點: E6-A207教室

演講者: 高孟駿 副教授（陽明交通大學資工系）

演講主題: Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost

講題大綱：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.

請研究所一年級的同學當天準時聽講