Laplacian eigenvalues and the maximum cut problem

DOI10.1007/BF01585184zbMath0797.90107OpenAlexW2092812429MaRDI QIDQ1319025

Publication date: 12 April 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585184

zbMATH Keywords

maximum cut weighted graph eigenvalue upper bound weakly bipartite graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Max $k$-cut and the smallest eigenvalue, Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs, Mathematical Programming Models and Exact Algorithms, Using the eigenvalue relaxation for binary least-squares estimation problems, Applications of cut polyhedra. II, SOS Is Not Obviously Automatizable, Even Approximately, The expected relative error of the polyhedral approximation of the max- cut problem, On a positive semidefinite relaxation of the cut polytope, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Are Stable Instances Easy?, Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, Solving the max-cut problem using eigenvalues, A projection technique for partitioning the nodes of a graph, A recipe for semidefinite relaxation for $(0,1)$-quadratic programming, Semidefinite programming in combinatorial optimization, New algorithms for the weighted maximum cut problem on graphs, Discrete dynamical system approaches for Boolean polynomial optimization, Laplacian spectra and spanning trees of threshold graphs, The Maximum k-Colorable Subgraph Problem and Related Problems, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, Small bipartite subgraph polytopes, Combining semidefinite and polyhedral relaxations for integer programs, Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem, New bounds for the $\max$-$k$-cut and chromatic number of a graph, Algebraic connectivity and disjoint vertex subsets of graphs, New results for MaxCut in H$H$‐free graphs, A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach, Best ellipsoidal relaxation to solve a nonconvex problem., Edge cover by connected bipartite subgraphs, On duality gap in binary quadratic programming, Laplacian eigenvalues and fixed size multisection, Elliptic approximations of propositional formulae, New bounds on the unconstrained quadratic integer programming problem, On graphs with adjacency and signless Laplacian matrices eigenvectors entries in $\{-1,+1\}$, Diffusion bank networks and capital flows, On Laplacian spectra of parametric families of closely connected networks with application to cooperative control, Max-cut and extendability of matchings in distance-regular graphs, Laplace eigenvalues of graphs---a survey, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, A survey of automated conjectures in spectral graph theory, Maximum cut in fuzzy nature: models and algorithms, Semidefinite programming and combinatorial optimization, On the gap between the quadratic integer programming problem and its semidefinite relaxation, Parametric Lagrangian dual for the binary quadratic programming problem, New quadratic models for the maximum weighted cut problem, Spectral bounds for unconstrained $(- 1,1)$-quadratic optimization problems, Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs, Semidefinite relaxations for partitioning, assignment and ordering problems, Phase recovery, MaxCut and complex semidefinite programming, The Laplacian spectral radius of a graph under perturbation, Semidefinite relaxations for partitioning, assignment and ordering problems, Checking robust nonsingularity is NP-hard, Rank Optimality for the Burer--Monteiro Factorization, Spectral bounds for the maximum cut problem, Sherali-adams strikes back, Spectral partitioning with multiple eigenvectors, On Khot’s unique games conjecture, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Strict Complementarity in Semidefinite Optimization with Elliptopes Including the MaxCut SDP, Scalable Semidefinite Programming, Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT, Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality, Unnamed Item, Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, A randomized approximation scheme for metric MAX-CUT, The product of two high-frequency graph Laplacian eigenfunctions is smooth, Node and edge relaxations of the max-cut problem

Cites Work