Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems

DOI10.1016/j.ejor.2010.02.042zbMath1205.90213OpenAlexW2026101846MaRDI QIDQ992570

Walid Ben-Ameur, José Neto

Publication date: 9 September 2010

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2010.02.042

zbMATH Keywords

semidefinite programmingunconstrained quadratic programmingmaximum cut problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Quadratic programming (90C20)

Related Items (4)

A class of spectral bounds for max \(k\)-cut ⋮ A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems ⋮ From Graph Orientation to the Unweighted Maximum Cut ⋮ Spectral bounds for graph partitioning with prescribed partition sizes

Uses Software

• plantri

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems
• Combinatorial properties and the complexity of a max-cut approximation
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Laplacian eigenvalues and the maximum cut problem
• The cut polytope and the Boolean quadric polytope
• Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
• On the gap between the quadratic integer programming problem and its semidefinite relaxation
• Via Minimization with Pin Preassignments and Layer Preference
• Spectral bounds for the maximum cut problem
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Paths in graphs
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• On the integrality ratio of semidefinite relaxations of MAX CUT
• Selected Topics in Column Generation
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• A polynomial case of unconstrained zero-one quadratic optimization

This page was built for publication: Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems