4 ms·
There are tons of applications, but many of them come down to variations on breaking up some universe of things to minimize the downsides of breaking them up.
by KMag 6y ago
There are tons of applications, but many of them come down to variations on breaking up some universe of things to minimize the downsides of breaking them up.
If you have a bunch of chat users and a bunch of chat servers, and you want to figure out how to assign users to servers in a way that minimizes the number of messages going between your chat servers, then you're solving a min cut problem on a graph where users are nodes, edges are communications, and edge weights are communications volumes. Any links that you cut in order to partition the graph end up being cross-server traffic.
- at_a_remove 6y agoThank you. That's really an excellent example. I recall the early days of IRC networks being plagued by frequent "splits" as different chunks of the graph became disconnected, which was largely a result of the architecture of the servers and is probably the worst-case scenario for this sort of thing, but your example is immediately graspable.