Carnegie Mellon University
Browse

A Generalized Cheeger Inequality

Download (84.49 kB)
journal contribution
posted on 2008-07-01, 00:00 authored by Ioannis Koutis, Gary L. Miller, Richard Peng

The generalized conductance ϕ(G,H) between two graphs G and H on the same vertex set Vis defined as the ratio

ϕ(G,H)=minS⊆VcapG(S,S¯)capH(S,S¯),

where capG(S,S¯) is the total weight of the edges crossing from S to S¯=V−S. We show that the minimum generalized eigenvalue λ(LG,LH) of the pair of Laplacians LG and LH satisfies

λ(LG,LH)≥ϕ(G,H)ϕ(G)/8,

where ϕ(G) is the usual conductance of G. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to λ(LG,LH). The inequality complements a recent proof that ϕ(G) cannot be replaced by Θ(ϕ(G,H)) in the above inequality, unless the Unique Games Conjecture is false.

History

Publisher Statement

© ACM, 2008. This is the authors’ version of the work. It is posted here by permission of the ACM for your personal use. Not for redistribution. The definitive version was published in: Proc. of the 2008 International Conference on Image and Video Retrieval CIVR’08, July 7–9, 2008, Niagara Falls, Canada. http://doi.acm.org/10.1145/1386352.1386405

Date

2008-07-01

Usage metrics

    Categories

    Keywords

    computer sciencesInformation and Computing Sciences not elsewhere classified

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC