Hacker News Reader

Comment by krastanov | Hacker News Reader

This is a bit like asking what is matrix diaginalization used for. The applications are much too numerous in many different fields of science and engineering. "Graph partition" problems generally search for ways to separate a graph into subgraphs such that some measure is optimized. E.g. resilience of network connections, immunizations, some error correction algorithms, optimizing flow of stuff through nodes, logistics. This list probably barely scratches the surface.

Edit: my comment sounds a bit rude on second read. My apologies, it is the limitations of this medium.

View on HN

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.

Thank 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.

Thanks. I wasnt being snarky. I really didn't know what such algorithms are used for and the paper didn't mention examples either.

This problem is assumed to be common knowledge among graph theory specialists.

Everyone on Hacker News is not assumed to be graph theory specialists.

That's assumed common knowledge for non-graph theory specialists.

I would say it's common knowledge for anyone with a CS degree.

its a bit advanced. Many university curriculums just skim through max flow min cut algorithms in a week or two as part of the algorithms class.

Isn’t graph partition a form of diagonalization?

What is the relationship? I guess most of us are not spectral graph theory experts. Are you looking at the adjacency matrix or the Laplacian matrix?

http://www.math.ucsd.edu/~fan/talks/mlg.pdf

Okay yeah, Cheeger's inequality and all those are straight up graduate-level theoretical computer science. Definitely not something you can just throw into a discussion assuming people know what you're talking about!

Reply on news.ycombinator.com