A class of spectral bounds for Max k-cut

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

Abstract: Let G be an undirected and edge-weighted simple graph. In this paper we introduce a class of bounds for the maximum k-cut problem in G. Their expression notably involves eigenvalues of the weight matrix together with some other geometrical parameters (distances between a discrete point set and a linear subspace). This extends a bound recently introduced by Nikiforov. We also show cases when the provided bounds strictly improve over other eigenvalue bounds from the literature.

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

Category 1: Combinatorial Optimization (Approximation Algorithms )

Citation:

Download: [PDF]

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

Modify/Update this entry