Parallel time complexity of a heuristic algorithm for the k-center problem with usage weights

The authors analyze the parallel time-complexity of a heuristic algorithm for solving the NP-hard k-center problem with usage weights. The problem is to choose k vertices as service centers so that the maximum weighted service delivery distance to any vertex is minimized. The algorithm uses a greedy strategy to choose the vertex with maximum usage weights as the next service vertex. It generates results that are guaranteed to be no greater than twice the optimal solution values, which is the best possible polynomial time heuristic unless P=NP, and its uniprocessor time complexity is O(n ³). The authors show that the algorithm may be implemented on a multiprocessor system in O(n log² n) time, where n is the total number of vertices. They further show that even with unlimited parallelism, this algorithm will have higher than polylogarithmic time complexity unless polylogspace=P