Optimization Online


A class of spectral bounds for Max k-cut

Miguel F. Anjos(anjos***at***stanfordalumni.org)
Josť Neto(Jose.Neto***at***telecom-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 )


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society