Squared Metric Facility Location Problem

Details Squared Metric Facility Location Problem Squared Metric Facility Location Problem

2011-11-07

arxiv.org/abs/1111.1672v2

Computer Science

Data Structures and Algorithms

New analysis of Chudak and Shmoys's algorithm

Scientific paper

We consider a generalization of the Squared Euclidean Facility Location Problem, when the distance function is a squared metric, which we call Squared Metric Facility Location Problem (SMFLP). We show that there is no approximation algorithm with factor better than 2.04 for the SMFLP, assuming P \neq NP. We analyze the best known algorithms for the Metric Facility Location Problem (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 is the best possible for SMFLP. Also, we propose a new technique to systematically bound factor-revealing programs, and use it in the dual-fitting analysis of the primal-dual algorithms for both the SMFLP and the MFLP, simplifying and improving some of the previous analysis for the MFLP.

Affiliated with

Also associated with

No associations

Rating

Squared Metric Facility Location Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Squared Metric Facility Location Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Squared Metric Facility Location Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692990