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


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


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