5 ms·
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. "
by krastanov 6y ago
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.
- vsskanth 6y agoThanks. I wasnt being snarky. I really didn't know what such algorithms are used for and the paper didn't mention examples either.
- anticensor 6y agoThis problem is assumed to be common knowledge among graph theory specialists.
- Fordec 6y agoEveryone on Hacker News is not assumed to be graph theory specialists.
- strictfp 6y agoThat's assumed common knowledge for non-graph theory specialists.
- bosswipe 6y agoI would say it's common knowledge for anyone with a CS degree.
- aliahsan07 6y agoits 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.
- adamnemecek 6y agoIsn’t graph partition a form of diagonalization?
- mehrdadn 6y agoWhat 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?
- adamnemecek 6y agohttp://www.math.ucsd.edu/~fan/talks/mlg.pdf http://www.math.ucsd.edu/~fan/talks/mlg.pdf
- mehrdadn 6y agoOkay 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!
- KMag 6y agoThere 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.