# Local Search vs K-means Clustering

Artificial Intelligence Asked by KGhatak on September 5, 2020

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:

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

## Related Questions

### Should I use the discounted average reward as objective in a finite-horizon problem?

0  Asked on December 18, 2020 by lll

### What is the search depth of AlphaGo and AlphaGo Zero?

1  Asked on December 15, 2020

### Why does the error of my LSTM not decrease after 10 epochs?

1  Asked on December 13, 2020 by k-do

### Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?

1  Asked on December 9, 2020 by kais-hasan

### Is it good practice to save NLP Transformer based pre-trained models into file system in production environment

0  Asked on December 9, 2020 by murugesh

### Why is my Soft Actor-Critic’s policy and value function losses not converging?

1  Asked on December 7, 2020 by zahra

### Can you train Transformers sequentially?

1  Asked on December 5, 2020

### What is meant by “ground truth” in the context AI?

2  Asked on December 3, 2020 by mscott

### Utilizing continuous variables in concept learning algorithms

0  Asked on December 3, 2020 by edwin-carlsson

### Unix timestamps for Recurrent Neural Networks

1  Asked on December 2, 2020 by alena-volkova

### Is it possible to implement Asimov’s Three Laws of Robotics?

3  Asked on November 30, 2020 by mithical

### Is there any research on developing AGI systems based on meta-programming?

0  Asked on November 30, 2020 by dimer

### Extracting algebraic constraints from the input data

3  Asked on November 18, 2020 by user91411

### Any AI software to help finding funding for AI projects?

0  Asked on November 18, 2020 by basile-starynkevitch

### Understaning Bayesian Optimisation graph

1  Asked on November 7, 2020 by duttaa

### Does Algorithmic Mechanism Design come under the field of AI?

0  Asked on October 30, 2020 by kosmos

### How can I implement 2D CNN filter with channelwise-bound kernel weights?

1  Asked on October 12, 2020 by petsol

### Why L2 loss is more commonly used in Neural Networks than other loss functions?

1  Asked on September 27, 2020 by ali-khalili

### How to produce documents like factset blackline?

1  Asked on September 23, 2020 by user2946825

### How large should the corpus be to optimally retrain the GPT-2 model?

0  Asked on September 20, 2020 by andreas-torester