A facility location problem

Consider the following scenario. There are N localities in a town where population for locality $L_i$ is denoted by $P_i$, $i \in {1,\ldots,n}$. We need to place K hospitals around the town in a way that the cost of accessing the hospital is minimized.

We are basically trying to
$$\min_O(\sum_{i=1}^N P_i \times C(d(L_i,O(L_i))))$$
where, $$O(L_i) = \textrm{Nearest hospital's location to }L_i\\d=\textrm{Euclidean distance between 2 locations}\\C = \textrm{Cost function to travel distance }``d"$$

It doesn't seem we can use gradient descent. Consider 3 localities $L_1,L_2$ and $L_3$ and 2 hospitals $H_1,H_2$. If we initially put $H_1,H_2$ on $L_1,L_2$ e.g.

$$L_1H_1\ldots L_2H_2 \ldots L_3$$

If the gradient descent starts moving projects to the right, then we may find ourselves in the following situation. The final location of nearest hospital to $L_2$ would have changed from $H_2$ to $H_1$.

$$L_1\ldots H_1L_2 \ldots H_2L_3$$

So could you please give me some pointers on how to solve this problem?

This problem is known as Euclidean $k$-center problem and is known to be NP-complete. There are some approximation algorithms but we don't have any PTAS algorithm.

Of course for $K \geq N$, the solution is trivial, with optimal value 0.

StackExchange Computer Science Q#52645, answer score: 2