比利时vs摩洛哥足彩
,
university of california san diego
****************************
food for thought seminar
franklin kenter
rice university
eigenvector norms matter in spectral graph theory
abstract:
we investigate the role of eigenvector norms in spectral graph theory to various combinatorial problems including the densest subgraph problem, the cheeger constant, among others. we introduce randomized spectral algorithms that produce guarantees which, in some cases, are better than the classical spectral techniques. in particular, we will give an alternative cheeger “sweep†(graph partitioning) algorithm which provides a linear spectral bound for the cheeger constant at the expense of an additional factor determined by eigenvector norms. finally, we apply these ideas and techniques to problems and concepts unique to directed graphs.
december 18, 2014
10:00 am
ap&m b412
****************************