Next: MAXIMUM K-FACILITY LOCATION
Previous: MAXIMUM K-FACILITY DISPERSION
symmetric and satisfy the triangle inequality,
locations where a facility may be built,
a nonnegative cost f(v) of building a facility at v,
for each location
a nonnegative demand d(v).
Locations for the facilities to be built, i.e., .
- Good News:
Approximable within 2.408 .
- Bad News:
Transformation from MINIMUM VERTEX COVER in bounded degree graphs.
Not approximable within 1.463 unless NP
If f(v)=1 for every
the same hardness results are valid, but
the problem is approximable within 2.225.
If F=V and f(v)=1 then the problem is approximable within 2.104 but
not within 1.278 unless NP
The generalization to unrestricted cost functions c is approximable