A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems (Q747779)
From MaRDI portal
scientific article; zbMATH DE number 6101538
- A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems |
scientific article; zbMATH DE number 6101538 |
|
Statements
A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems (English)
0 references
A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems (English)
0 references
19 October 2015
0 references
2 November 2012
0 references
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\).
0 references
approximation algorithm
0 references
bound-factor revealing linear program
0 references
facility location
0 references
