Changes

We show that there is a novel and simple decomposition of an input point set P into small subsets P_i, such that:

We show that there is a novel and simple decomposition of an input point set P into small subsets P_i, such that:

1- the cost of solving the facility location problem for each P_i is small (which means that for each P_i one needs to open only a small, polylogarithmic number of facilities),

1- the cost of solving the facility location problem for each P_i is small (which means that for each P_i one needs to open only a small, polylogarithmic number of facilities),

2- sum_i opt(P_i) \le (1+eps)  opt(P), where for a point set P, opt(P) denotes the cost of an optimal solution for P.

2- sum_i opt(P_i) \le (1+eps)  opt(P), where for a point set P, opt(P) denotes the cost of an optimal solution for P.

Using this decomposition we obtain two main results:

Using this decomposition we obtain two main results: