Approximating activation edge-cover and facility location problems
share
What approximation ratio can we achieve for the Facility Location problem if whenever a client u connects to a facility v,the opening cost of v is at most θ times the service cost of u? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph G=(V,E), a set R ⊆ V of terminals, and thresholds {t^e_u,t^e_v} for each uv-edge e ∈ E. The goal is to find an assignment a={a_v:v ∈ V} to the nodes minimizing ∑_v ∈ V a_v, such that the edge set E_ a={e=uv: a_u ≥ t^e_u, a_v ≥ t^e_v} activated by a covers R. We obtain ratio 1+ω(θ) ≈θ-θ for the problem, where ω(θ) is the root of the equation x+1=(θ/x) and θ is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get that the above variant of Facility Location admits ratio 1+ω(θ); if for each facility all service costs are identical then we show a better ratio 1+_k ≥ 1H_k-1/1+k/θ, where H_k=∑_i=1^k 1/i. For the Min-Power Edge-Cover problem we improve the ratio 1.406 of Calinescu et. al. (achieved by iterative randomized rounding) to 1+ω(1)<1.2785. For unit thresholds we improve the ratio 73/60 ≈ 1.217 to 1555/1347≈ 1.155.
READ FULL TEXT