-

 

 

 




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 )

Citation:

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

 

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