A class of spectral bounds for Max k-cut

Miguel F. Anjos (anjosstanfordalumni.org)
José Neto (Jose.Netotelecom-sudparis.eu)

Abstract: 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 the literature. We also report computational results illustrating the potential impact of the new bounds.

Keywords: Max k-cut, Adjacency matrix eigenvalues, Adjacency matrix eigenvectors

Category 1: Combinatorial Optimization (Approximation Algorithms )

Citation: https://doi.org/10.1016/j.dam.2019.10.002

Download:

Entry Submitted: 12/18/2017
Entry Accepted: 12/31/2018
Entry Last Modified: 11/26/2019

Modify/Update this entry