A note on two source location problems

We consider Source Location   (SLSL) problems: given a capacitated network G=(V,E)G=(V,E), cost c(v)c(v) and a demand d(v)d(v) for every v∈Vv∈V, choose a min-cost S⊆VS⊆V so that λ(v,S)⩾d(v)λ(v,S)⩾d(v) holds for every v∈Vv∈V, where λ(v,S)λ(v,S) is the maximum flow value from v to S  . In the directed variant, we have demands din(v)din(v) and dout(v)dout(v) and we require λ(S,v)⩾din(v)λ(S,v)⩾din(v) and λ(v,S)⩾dout(v)λ(v,S)⩾dout(v). Undirected SLSL is (weakly) NP-hard on stars with r(v)=0r(v)=0 for all v   except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected SLSL admit a (lnD+1)(lnD+1)-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected SLSL on trees with running time O(|V|Δ3)O(|V|Δ3), where Δ=maxv∈Vd(v)Δ=maxv∈Vd(v). This algorithm is used to derive a linear time algorithm for undirected SLSL with Δ⩽3Δ⩽3. We also consider the Single Assignment Source Location   (SASLSASL) where every v∈Vv∈V should be assigned to a single node s(v)∈Ss(v)∈S. While the undirected SASLSASL is in P, we give a (ln|V|+1)(ln|V|+1)-approximation algorithm for the directed case, and show that this is tight, unless P = NP.