Local Search vs K-means Clustering

I have found that the K-means algorithm with K=20, has been mentioned as a solution for the below question,

A new mobile phone service chain store would like to open 20 service
centers in your city. Each service center should cover at least one
shopping center and 5000 households of annual income over $75000.
Design a scalable algorithm that decides locations of service centere
by taking all the aforementioned constraints into consideration.

However, I think Local Search algorithm, similar to solving N-Queen problem by local searches, can also be an alternate solution. In fact, below is the algorithm that I have in mind,

My Algorithm:

//Define constraints 
//  CT1 as - should cover at at least one shopping center, and 
//  and CT2 as - should cover 5000 households with min income 75K/anum

//Initialize locations of the service centers C_i for i=1,..,20
for i=1 to 20
    C_i := randomly select location from map
end-for
//Iterate until cut-off T
for t=1 to T //T may be initialized with 1000
    C_r := randomly select any of {C_1,..,C_20} such that they are currently not satisfying the constraints CT_1 and CT_2
    if C_r is NULL$
         return success //current assignments of C_1 to C_20 are valid
    else
         Assign C_r a new location that has lowest conflict w.r.t. CT_1 and CT_2
    end-if
end-for

Further, in support of my suggestion, I have found quite a few papers that are suggesting that the local search is a better approximation. Few of such papers are:

• A Local Search Approximation Algorithm for k-Means Clustering, Tapas
  Kanungo et al
• A Better k-means++ Algorithm via Local Search,
  Silvio Lattanzi & Christian Sohler

Would you share your thoughts on the feasibility of the local search algorithm provided above, as a potential solution.