TY - GEN

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

AU - Kao, Mong Jen

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85170082524&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85170082524

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1071

EP - 1089

BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

PB - Association for Computing Machinery

T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

Y2 - 22 January 2023 through 25 January 2023

ER -