A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems (Q747779): Difference between revisions

The paper describes a systematic approach for obtaining upper bound-factor revealing linear programs. The authors apply this technique to the metric facility location problem (MFLP) and the squared metric facility location problem (SMFLP). They prove that unless \(P \neq NP\), there is no approximation factor better than \(2.04\). They show that an LP-rounding algorithm for MFLP when applied to SMFLP achieves the best possible ratio of \(2.04\).