- | ||||
|
![]()
|
A class of spectral bounds for Max k-cut
Miguel F. Anjos (anjos 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 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 | |
![]() |