On the Capacitated Facility Location Problem and LP-based ResultsOberseminar Discrete Optimization

by Mong-Jen Kao (National Yang-Ming Chiao-Tung University, Taiwan)

Monday May 11, 2026, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

The study of classic covering and location problems with the concept of limited capacity supply has emerged in the past two decades and drawn wide attention with a series of algorithmic results. In this talk I will introduce the capacitated facility location problem and relative algorithmic results.

First, the Multicommodity Flow Network (MFN) relaxation, developed in [An, Singh, Svensson, FOCS2014], is the only LP relaxation known to provide a constant integrality gap for the classic capacitated facility location (CFL) problem in polynomial time. I will introduce this relaxation and the best known integrality gap of it. Secondly, the variant with uniform facility cost is an indicator variation between the general CFL problem and the classic uncapacitated facility location problem. I will briefly talk about the results known for this problem and its connection to the long-standing capacitated k-median problem.

 

The Oberseminar takes place in the Seminarraum, 1st floor. Participants are invited to have coffee or tea in the lounge before.