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

Mong Jen Kao*

*此作品的通信作者

研究成果: Conference contribution同行評審

1 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
發行者Association for Computing Machinery
頁面1071-1089
頁數19
ISBN(電子)9781611977554
出版狀態Published - 2023
事件34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
持續時間: 22 1月 202325 1月 2023

出版系列

名字Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
國家/地區Italy
城市Florence
期間22/01/2325/01/23

指紋

深入研究「On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem」主題。共同形成了獨特的指紋。

引用此