Approximation of the Stability Number of a Graph via Copositive Programming
From MaRDI portal
Publication:2784442
DOI10.1137/S1052623401383248zbMath1035.90058WikidataQ56874386 ScholiaQ56874386MaRDI QIDQ2784442
Etienne de Klerk, Dimitrii V. Pasechnik
Publication date: 23 April 2002
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Semidefinite programming (90C22) Convex programming (90C25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Matrix Relaxations in Combinatorial Optimization, Mathematical Programming Models and Exact Algorithms, Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone, Improved Conic Reformulations for $K$-means Clustering, Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph, 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, Completely positive factorization by a Riemannian smoothing method, Homogenization for polynomial optimization with unbounded sets, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, A Sum of Squares Characterization of Perfect Graphs, Dehomogenization for completely positive tensors, Characterization of polynomials whose large powers have all positive coefficients, Least Squares Approximation to the Distribution of Project Completion Times with Gaussian Uncertainty, Optimization under uncertainty and risk: quadratic and copositive approaches, On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity, (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, Graph isomorphism: physical resources, optimization models, and algebraic characterizations, A Geometrical Analysis on Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems, Approximation of the Shannon capacity via matrix cone programming, Unnamed Item, Disruption Risk Mitigation in Supply Chains: The Risk Exposure Index Revisited, DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization, An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming, A new branch-and-bound algorithm for standard quadratic programming problems, Contribution of copositive formulations to the graph partitioning problem, Foundations of Set-Semidefinite Optimization, A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors, Gap, cosum and product properties of the θ′ bound on the clique number, Copositivity tests based on the linear complementarity problem, A characterization of the weighted Lovász number based on convex quadratic programming, Optimality conditions for linear copositive programming problems with isolated immobile indices, Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls, Robust Quadratic Programming with Mixed-Integer Uncertainty, Depth-first simplicial partition for copositivity detection, with an application to MaxClique, On LP-based approximation for copositive formulation of stable set problem, A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem, On Degenerate Doubly Nonnegative Projection Problems, On the accuracy of uniform polyhedral approximations of the copositive cone, Cutting planes for semidefinite relaxations based on triangle-free subgraphs, On NP-hardness of the clique partition -- independence number gap recognition and related problems, Copositive and semidefinite relaxations of the quadratic assignment problem, On standard quadratic programs with exact and inexact doubly nonnegative relaxations, Conic formulations of graph homomorphisms, 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, The difference between \(5\times 5\) doubly nonnegative and completely positive matrices, Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials, On conic QPCCs, conic QCQPs and completely positive programs, Bounding the separable rank via polynomial optimization, Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets, 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, Certifying the global optimality of quartic minimization over the sphere, 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, Matrices with high completely positive semidefinite rank, A copositive formulation for the stability number of infinite graphs, LP-based tractable subcones of the semidefinite plus nonnegative cone, Extended and discretized formulations for the maximum clique problem, A linear programming reformulation of the standard quadratic optimization problem, On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, A note on the Lasserre hierarchy for different formulations of the maximum independent set problem, A characterization of Delsarte's linear programming bound as a ratio bound, A factorization method for completely positive matrices, Semidefinite bounds for the stability number of a graph via sums of squares of polynomials, Immobile indices and CQ-free optimality criteria for linear copositive programming problems, Generating irreducible copositive matrices using the stable set problem, Sparse solutions to random standard quadratic optimization problems, Moment approximations for set-semidefinite polynomials, Semidefinite approximations for quadratic programs over orthogonal matrices, A note on set-semidefinite relaxations of nonconvex quadratic programs, A primal barrier function phase I algorithm for nonsymmetric conic optimization problems, 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, The boosted DC algorithm for linearly constrained DC programming, Interiors of completely positive cones, Separating doubly nonnegative and completely positive matrices, Separation and relaxation for cones of quadratic forms, Copositive optimization -- recent developments and applications, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, An improved algorithm to test copositivity, An algorithm for determining copositive matrices, Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision, Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization, Copositive programming via semi-infinite optimization, Factorization and cutting planes for completely positive matrices by copositive projection, Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, On the computational complexity of membership problems for the completely positive cone and its dual, 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, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, Exploiting equalities in polynomial programming, The \(\mathcal A\)-truncated \(K\)-moment problem, Analysis of copositive optimization based linear programming bounds on standard quadratic optimization, Effective Pólya semi-positivity for non-negative polynomials on the simplex, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, An axiomatic duality framework for the theta body and related convex corners, Linear conic formulations for two-party correlations and values of nonlocal games, Optimization over structured subsets of positive semidefinite matrices via column generation, A robust Lagrangian-DNN method for a class of quadratic optimization problems, Algorithmic copositivity detection by simplicial partition, Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems, Stability of polytopes of matrices via affine parameter-dependent Lyapunov functions: asymptotically exact LMI conditions, Quadratic factorization heuristics for copositive programming, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation, Pólya's theorem with zeros, A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Polyhedral approximations of the semidefinite cone and their application, A MAX-CUT formulation of 0/1 programs, Alternative SDP and SOCP approximations for polynomial optimization, Copositive Programming, Simple ingredients leading to very efficient heuristics for the maximum clique problem, Lower bounds on nonnegative rank via nonnegative nuclear norms, 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, Searching for critical angles in a convex cone, A quantitative Pólya's theorem with zeros, An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs, On the \(k\)-independence number of graphs, Complexity aspects of local minima and related notions, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, On upper bounding Shannon capacity of graph through generalized conic programming, On the complexity of finding a local minimizer of a quadratic function over a polytope, Continuous cubic formulations for cluster detection problems in networks, On an extension of Pólya's Positivstellensatz, D.C. versus copositive bounds for standard QP, Completely positive reformulations for polynomial optimization, Exploiting symmetry in copositive programs via semidefinite hierarchies, A note on completely positive relaxations of quadratic problems in a multiobjective framework, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme, A dynamic inequality generation scheme for polynomial programming, A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
