VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
Celotno besedilo
  • Eigenvalue and semidefinite approximations for graph partitioning problem
    Povh, Janez, 1973-
    Partitioning the nodes of the graph into sets with prescribed cardinalities is an NP-hard problem. Solving it to optimality often relies on good lower bounds. Donath and Hoffman and later also Rendl ... and Wolkowicz presented lower bounds which are based on graph eigenvalues. We show how to rewrite the graph partitioning problem as a linear program over the cone of complete positive matrices and then analyze the semidefinite lower bounds, obtained by relaxing the copositive program. We show that these new lower bounds are significantly tighter than existing spectral and semidefinite lower bounds.
    Vir: SOR '07 proceedings (Str. 95-100)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2007
    Jezik - angleški
    COBISS.SI-ID - 14406233