Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
From MaRDI portal
Publication:5444282
DOI10.1137/05064401XzbMath1176.90611OpenAlexW2162579105WikidataQ58051170 ScholiaQ58051170MaRDI QIDQ5444282
Luis F. Zuluaga, Juan Carlos Vera, Javier F. Peña
Publication date: 25 February 2008
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/05064401x
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Linear programming (90C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (54)
Cutting planes for semidefinite relaxations based on triangle-free subgraphs ⋮ On standard quadratic programs with exact and inexact doubly nonnegative relaxations ⋮ Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems ⋮ Computing the distance between the linear matrix pencil and the completely positive cone ⋮ Copositive programming motivated bounds on the stability and the chromatic numbers ⋮ Copositivity cuts for improving SDP bounds on the clique number ⋮ On the copositive representation of binary and continuous nonconvex quadratic programs ⋮ On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph ⋮ Extended and discretized formulations for the maximum clique problem ⋮ SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY ⋮ An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix ⋮ Semidefinite bounds for the stability number of a graph via sums of squares of polynomials ⋮ Generating irreducible copositive matrices using the stable set problem ⋮ Approximating the cone of copositive kernels to estimate the stability number of infinite graphs ⋮ Scaling relationship between the copositive cone and Parrilo's first level approximation ⋮ A new certificate for copositivity ⋮ A new approximation hierarchy for polynomial conic optimization ⋮ Copositivity and constrained fractional quadratic problems ⋮ A Sum of Squares Characterization of Perfect Graphs ⋮ Optimization under uncertainty and risk: quadratic and copositive approaches ⋮ Interiors of completely positive cones ⋮ (Global) optimization: historical notes and recent developments ⋮ Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems ⋮ Approximation hierarchies for copositive cone over symmetric cone and their comparison ⋮ Approximation of the Shannon capacity via matrix cone programming ⋮ Separating doubly nonnegative and completely positive matrices ⋮ Copositive optimization -- recent developments and applications ⋮ Copositive tensor optimization problem and its applications to hypergraphs ⋮ Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization ⋮ An improved algorithm to test copositivity ⋮ Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization ⋮ Factorization and cutting planes for completely positive matrices by copositive projection ⋮ New approximations for the cone of copositive matrices and its dual ⋮ New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability ⋮ Testing copositivity via mixed-integer linear programming ⋮ Handelman's hierarchy for the maximum stable set problem ⋮ A refined error analysis for fixed-degree polynomial optimization over the simplex ⋮ Analysis of copositive optimization based linear programming bounds on standard quadratic optimization ⋮ A new branch-and-bound algorithm for standard quadratic programming problems ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ Nonconvex min-max fractional quadratic problems under quadratic constraints: copositive relaxations ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Gap, cosum and product properties of the θ′ bound on the clique number ⋮ Copositive Programming ⋮ A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization ⋮ Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices ⋮ On the polyhedral lift-and-project methods and the fractional stable set polytope ⋮ An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs ⋮ On LP-based approximation for copositive formulation of stable set problem ⋮ Completely positive reformulations for polynomial optimization ⋮ Exploiting symmetry in copositive programs via semidefinite hierarchies ⋮ A dynamic inequality generation scheme for polynomial programming
Uses Software
This page was built for publication: Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
