AbstractThep-centre problem, or minimax location-allocation problem in location theory terminology, is the following: givenndemand points on the plane and a weight associated with each demand point, findpnew facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a givenpin time polynomial inn. Computational results are presented.