Laplacian eigenvalues and the maximum cut problem
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 4193718
- Max cut and the smallest eigenvalue
- Max CUT and the smallest eigenvalue
- Solving the max-cut problem using eigenvalues
- scientific article; zbMATH DE number 426360
- Max \(k\)-cut and the smallest eigenvalue
- Cut ratios and Laplacian eigenvalues
- Spectral bounds for the maximum cut problem
- Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
- On graphs with eigenvectors in \(\{-1,0,1\}\) and the max \(k\)-cut problem
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 4193718 (Why is no real title available?)
- scientific article; zbMATH DE number 3296351 (Why is no real title available?)
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Combinatorial properties and the complexity of a max-cut approximation
- Compositions in the bipartite subgraph polytope
- Experiments in quadratic 0-1 programming
- Geometric algorithms and combinatorial optimization
- Lower Bounds for the Partitioning of Graphs
- On Minimizing the Maximum Eigenvalue of a Symmetric Matrix
- On Transportation Problems with Upper Bounds on Leading Rectangles
- On some weakly bipartite graphs
- Solving the max-cut problem using eigenvalues
- The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
- Weakly bipartite graphs and the max-cut problem
Cited in
(77)- Discrete dynamical system approaches for Boolean polynomial optimization
- scientific article; zbMATH DE number 1484326 (Why is no real title available?)
- Scalable semidefinite programming
- Rank optimality for the Burer-Monteiro factorization
- A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
- On graphs with adjacency and signless Laplacian matrices eigenvectors entries in \(\{-1,+1\}\)
- Diffusion bank networks and capital flows
- Sherali-Adams strikes back
- The product of two high-frequency graph Laplacian eigenfunctions is smooth
- Weighted Laplacians and the sigma function of a graph
- New algorithms for the weighted maximum cut problem on graphs
- Algebraic connectivity and disjoint vertex subsets of graphs
- New results for MaxCut in H$H$‐free graphs
- An inequality for eigenvalues of symmetric matrices with applications to max-cuts and Graph Energy∗
- Sherali-adams strikes back
- Tighter spectral bounds for the cut size, based on Laplacian eigenvectors
- Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
- Laplacian spectra and spanning trees of threshold graphs
- Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs
- On Khot’s unique games conjecture
- Spectral bounds for the maximum cut problem
- Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
- On duality gap in binary quadratic programming
- New bounds on the unconstrained quadratic integer programming problem
- On a positive semidefinite relaxation of the cut polytope
- Maximum cut in fuzzy nature: models and algorithms
- Strict complementarity in semidefinite optimization with elliptopes including the maxcut SDP
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Are stable instances easy?
- Laplacian eigenvalues and fixed size multisection
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- A randomized approximation scheme for metric MAX-CUT
- Max \(k\)-cut and the smallest eigenvalue
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Spectral partitioning with multiple eigenvectors
- Combinatorial properties and the complexity of a max-cut approximation
- The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
- The Laplacian spectral radius of a graph under perturbation
- Semidefinite programming and combinatorial optimization
- Parametric Lagrangian dual for the binary quadratic programming problem
- Node and edge relaxations of the max-cut problem
- Phase recovery, MaxCut and complex semidefinite programming
- Small bipartite subgraph polytopes
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
- Edge cover by connected bipartite subgraphs
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- Best ellipsoidal relaxation to solve a nonconvex problem.
- SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
- Elliptic approximations of propositional formulae
- Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems
- An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach
- A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
- scientific article; zbMATH DE number 780784 (Why is no real title available?)
- Cut ratios and Laplacian eigenvalues
- Mathematical programming models and exact algorithms
- Applications of cut polyhedra. II
- New quadratic models for the maximum weighted cut problem
- Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
- On the gap between the quadratic integer programming problem and its semidefinite relaxation
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- Laplace eigenvalues of graphs---a survey
- Semidefinite programming in combinatorial optimization
- A survey of automated conjectures in spectral graph theory
- Max-cut and extendability of matchings in distance-regular graphs
- An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
- SOS is not obviously automatizable, even approximately
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- On Laplacian spectra of parametric families of closely connected networks with application to cooperative control
- The expected relative error of the polyhedral approximation of the max- cut problem
- Checking robust nonsingularity is NP-hard
- Solving the max-cut problem using eigenvalues
- Combining semidefinite and polyhedral relaxations for integer programs
- Using the eigenvalue relaxation for binary least-squares estimation problems
- A projection technique for partitioning the nodes of a graph
This page was built for publication: Laplacian eigenvalues and the maximum cut problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1319025)
