# 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

### Why are Target Networks used in Deep Q-Learning as opposed to the Expected Value equation?

1  Asked on September 10, 2020 by tmt

### Handling a Large Discrete Action Space in Deep Q Learning

0  Asked on September 9, 2020 by foxcharles

### What are the advantages and disadvantages of using LISP for constraint satisfaction in 3D space

1  Asked on September 7, 2020 by shashank-gargeshwari

### Local Search vs K-means Clustering

0  Asked on September 5, 2020 by kghatak

### What are the right algorithms for this open loop control problem

1  Asked on August 30, 2020 by toben-aus

### What is the state of the art solution for text classification for large corpora

0  Asked on August 22, 2020 by nick

### Non Max Suppression and Object Detection

1  Asked on August 16, 2020 by moe-kaung-kin

### Isn’t a simulation a great model for model-based reinforcement learning?

1  Asked on August 9, 2020 by ray-walker

### Correct problem statement for CNN. Stitching parts of the map

0  Asked on August 1, 2020 by green_wizard

### How can I predict the true label for data with incomplete features based on the trained model with data with more features?

0  Asked on July 26, 2020 by dae-young-park

### Why is Symbolic AI not so popular as ANN but used by IBM Deep Blue?

1  Asked on July 21, 2020 by datdinhquoc