Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem

We consider a location problem whose mathematical formulation is max s {z(S): S ⊆ N, |S| = K}, where z(S) = ∑ i∈I max j∈s c ij and C = (c ij ) is any non-negative m × n matrix with row index set I and column index set N. We show that any procedure which uses matrix C only to calculate values of the function z(S) cannot, with a number of values polynomial in n, guarantee to find an optimal solution. However when C is the edge-vertex incidence matrix of a graph, we show that if n is suitably large and K is fixed or does not grow too rapidly with n, the K vertices of largest degree nearly always constitute an optimal solution.