graph partition problem

Semidefinite programming and eigenvalue bounds for the graph partition problem

  • Renata Sotirov
  • Edwin van Dam
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the total weight of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes … Read more