max k-cut

A class of spectral bounds for Max k-cut

  • Miguel F. Anjos
  • José Neto
    • Categories Approximation Algorithms Tags , ,

    In this paper we introduce a new class of bounds for the maximum -cut problem on undirected edge-weighted simple graphs. The bounds involve eigenvalues of the weighted adjacency matrix together with geometrical parameters. They generalize previous results on the maximum (2-)cut problem and we demonstrate that they can strictly improve over other eigenvalue bounds from … Read more