  A systematic technique to bound factor-revealing linear programs is
presented. We show how to derive a family of upper bound factor-revealing
programs (UPFRP), and show that each such program can be solved by a computer
to bound the approximation factor of an associated algorithm. Obtaining an
UPFRP is straightforward, and can be used as an alternative to analytical
proofs, that are usually very long and tedious. We apply this technique to the
Metric Facility Location Problem (MFLP) and to a generalization where the
distance function is a squared metric. We call this generalization the Squared
Metric Facility Location Problem (SMFLP) and prove that there is no
approximation factor better than 2.04, assuming P $\neq$ NP. Then, we analyze
the best known algorithms for the MFLP based on primal-dual and LP-rounding
techniques when they are applied to the SMFLP. We prove very tight bounds for
these algorithms, and show that the LP-rounding algorithm achieves a ratio of
2.04, and therefore has the best factor for the SMFLP. We use UPFRPs in the
dual-fitting analysis of the primal-dual algorithms for both the SMFLP and the
MFLP, improving some of the previous analysis for the MFLP.
