On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem

Mong Jen Kao*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

The Multicommodity Flow Network (MFN) relaxation, developed in [An, Singh, Svensson, FOCS 2014], is the only polynomial-time solvable relaxation that is known to provide a bounded integrality gap for the classic capacitated facility location (CFL) problem. The best upper-bound known for the integrality gap of this strong LP relaxation, however, is in the order of 288. In this paper, we show that the MFN relaxation has an integrality gap at most (10 + √67)/2 ≈ 9.0927 for the CFL problem. This narrows down the range of the integrality gap to one digit. Our ingredient is an iterative rounding algorithm for this sophisticated LP relaxation.

Original languageEnglish
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Pages1071-1089
Number of pages19
ISBN (Electronic)9781611977554
StatePublished - 2023
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: 22 Jan 202325 Jan 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period22/01/2325/01/23

Fingerprint

Dive into the research topics of 'On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem'. Together they form a unique fingerprint.

Cite this