Cool! This was some great work, absolutely genius data structure wizardry. Not sure if your dad is still with us -- but if so, give him my regards, and tell him that he's awesome.
At 3:50, is the gain of vertices in the bucket given by the formula D = E-I where E is the external cost and I is the internal cost? The same way as in KL Algo(?) What is the formula for the cell gain in FM algo?
Hi -- our code isn't public yet -- maybe by the end of the year, or early next year. I'd suggest looking at the METIS distribution from Prof. George Karypis' group (please be sure to cite them correctly!). The multilevel hMetis is spectacular; I'm hoping to get a video on that work done shortly. glaros.dtc.umn.edu/gkhome/metis/metis/download
FM works well for bisection -- two roughly equal partitions. There's multi-way partitioner algorithms, but in my experience, repeatedly bisecting graphs produces better results that direct multi-way partitioning. I believe that hMetis produces multi-way partitions through repeated partitions, rather than going direct. There are a lot of local minima in partitioning; my view is that by going multi-way, the number of local minima increases, and it makes the problem harder.
This was my dad's heuristic :)
Cool! This was some great work, absolutely genius data structure wizardry. Not sure if your dad is still with us -- but if so, give him my regards, and tell him that he's awesome.
Really helpful, Thank You
At 3:50, is the gain of vertices in the bucket given by the formula D = E-I where E is the external cost and I is the internal cost? The same way as in KL Algo(?)
What is the formula for the cell gain in FM algo?
thank you prof.. you got a new sub
Hello
Thank you for your clear and simple explanation.
Could I have the code of F-M partitioning algorithm? I really need the code for my thesis
Hi -- our code isn't public yet -- maybe by the end of the year, or early next year. I'd suggest looking at the METIS distribution from Prof. George Karypis' group (please be sure to cite them correctly!). The multilevel hMetis is spectacular; I'm hoping to get a video on that work done shortly. glaros.dtc.umn.edu/gkhome/metis/metis/download
@@profmadden Thanks
@@atefehtanzadeh3829 did you try METIS? Even though I went through the Overview of METIS, I find it really hard to run on my machine!
Hi. I have another question! Is it for two partitions or multi partitions?
FM works well for bisection -- two roughly equal partitions. There's multi-way partitioner algorithms, but in my experience, repeatedly bisecting graphs produces better results that direct multi-way partitioning. I believe that hMetis produces multi-way partitions through repeated partitions, rather than going direct. There are a lot of local minima in partitioning; my view is that by going multi-way, the number of local minima increases, and it makes the problem harder.