Determine the location of a logistics center which is optimally close to its providers

Question

Excuse me if my question is not worded perfectly in mathematical terms. I don't have a strong math background.

So, here's the problem which has been brought up by a real-life situation:

For simplicity, assume the problem is one-dimensional. There's a straight road with several facilities that can be thought of as suppliers on this road. We want to pick one of these facilities such that it is optimally close to all available resources that it needs on the road. For example, if we have three facilities as below:

Facility 1:
Resource1: Available
Resource2: Not Available
Resource3: Available

Facility 2:
Resource1: Not Available
Resource2: Available
Resource3: Not Available

Facility 3:
Resource 1: Not Available
Resource 2: Not Available
Resource 3: Available

Facility 4:
Resource 1: Available
Resource 2: Not Available
Resource 3: Not Available

Then Facility 2 is a solution. Obviously, the solution does not have to be unique but at least one exists by brute forcing.

Is this a famous problem? Is there an algorithm for this with $O(n)$ or $O(n^2)$ complexity? I think solving it in $O(n^3)$ should be possible by brute force.

Answer 1

In the one-dimensional case you can compute the distance from each facility to each resource in $O(n\times r)$ time, where there are $n$ facilities and $r$ resources. The pseudocode is as follows:

for i in 1 : r:
    dist = inf
    for j in 1 : n:
        if (resource(i) is available at facility(j)):
            dist = 0
        else:
            dist = dist + 1
        end
        left_dist[i,j] = dist
    end
end

for i in 1 : r:
    dist = inf
    for j in n : -1 : 1:
        if (resource(i) is available at facility(j)):     
            dist = 0
        else:
            dist = dist + 1
        end
        right_dist[i,j] = dist
        shortest_dist[i,j] = min(left_dist[i,j], right_dist[i,j])
    end
end

That is, for each resource, start at one end, and compute the distance to the previous facility. In your example, for resource 1 this is 0 for the first facility, then increment by 1 each time until you reach facility 4. For resource 2, start with distance $\infty$ for the first facility, because you can't find resource 2 by decreasing the facility number. This takes $O(n\times r)$ operations. Then, repeat this, starting at the other end, and finally, work out which end is better to start at for each resource and facility. Then you can compute the total cost for each facility.