edd*_*yxu 3 algorithm graph-theory graph graph-algorithm
是否有一个实用的算法(非NP-hard)可以将图形切割成两个近似相等的子图形(例如,一个子图形具有40%-50%的顶点),同时证明切割是最小的在两个子图具有近似相同数量的顶点的情况下,可能的切割？
这并不是最稀疏的切割; 如Dasgupta,Papadimitriou和Vazirani的第8章所述,它是平衡切割,也是NP-hard .sparsest cut问题的规范版本不允许指定分区大小.
有两种关于图分区问题的研究:具有最坏情况近似保证的算法,其中Arora-Rao-Vazirani是您感兴趣的主要结果,而算法没有最坏情况保证,这些算法通过其实际性能进行评估(随机例子我没有经验:METIS).即使我不太了解它,我也倾向于引导你走向后一线工作; 先验,O(√logn)bicriteria近似不是一个非常有用的保证,并且可能会有一些非平凡的算法工程,以使ARV首先在大规模上正常运行.