-

 

 

 




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: 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


  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