演講公告

新聞標題：　( 2024-05-02 )

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

• 主講人：高孟駿教授(國立陽明交通大學資訊工程學系)

• 演講日期：2024年5月14日 13:30-14:20

• 演講地點：(光復校區) 科學一館223室

• 摘要內容：
  

  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.

• 相關檔案：Talk_20240514-1.pdf

go back