I came across this problem at work trying to decide the most efficient way to group services in processes. I don't have the right words to google it.

I will use shops as a metaphor.

Let's say you have N stores that you want to place in M shopping centers. For each pair of stores you have a count of how many times per day a person will walk from each store to each other store. When stores are placed in the same shopping center, the cost to walk between them is low, but when you have to walk between shopping centers, the cost is high. How do you place the stores to minimize the total cost? (Let's assume that every shopping center needs to have N/M stores in it)

Right now I'm thinking you can represent each store as a node on a graph and then each node would have an edge (both ways) to ever other node. Then you want to somehow combine the N nodes in the graph into M big nodes so that they have some internal travel cost, and some external travel cost.

Does this problem have a name (like traveling salesman etc)? Are there existing algorithms to solve it? What words do I google?


This is called the quadratic assignment problem. The traveling salesman problem is a special case.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.