Approximation of the Stability Number of a Graph via Copositive Programming

From MaRDI portal
Revision as of 16:16, 3 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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)




Related Items (only showing first 100 items - show all)

On the accuracy of uniform polyhedral approximations of the copositive coneCutting planes for semidefinite relaxations based on triangle-free subgraphsOn NP-hardness of the clique partition -- independence number gap recognition and related problemsCopositive and semidefinite relaxations of the quadratic assignment problemOn standard quadratic programs with exact and inexact doubly nonnegative relaxationsConic formulations of graph homomorphismsSymmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problemsComputing the distance between the linear matrix pencil and the completely positive coneThe difference between \(5\times 5\) doubly nonnegative and completely positive matricesOptimization over the Boolean hypercube via sums of nonnegative circuit polynomialsOn conic QPCCs, conic QCQPs and completely positive programsBounding the separable rank via polynomial optimizationImproved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact setsCopositive programming motivated bounds on the stability and the chromatic numbersCopositivity cuts for improving SDP bounds on the clique numberOn the copositive representation of binary and continuous nonconvex quadratic programsCertifying the global optimality of quartic minimization over the sphereOn the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matricesConstraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problemMatrices with high completely positive semidefinite rankA copositive formulation for the stability number of infinite graphsLP-based tractable subcones of the semidefinite plus nonnegative coneExtended and discretized formulations for the maximum clique problemA linear programming reformulation of the standard quadratic optimization problemOn the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible setsA note on the Lasserre hierarchy for different formulations of the maximum independent set problemA characterization of Delsarte's linear programming bound as a ratio boundA factorization method for completely positive matricesSemidefinite bounds for the stability number of a graph via sums of squares of polynomialsImmobile indices and CQ-free optimality criteria for linear copositive programming problemsGenerating irreducible copositive matrices using the stable set problemSparse solutions to random standard quadratic optimization problemsMoment approximations for set-semidefinite polynomialsSemidefinite approximations for quadratic programs over orthogonal matricesA note on set-semidefinite relaxations of nonconvex quadratic programsA primal barrier function phase I algorithm for nonsymmetric conic optimization problemsApproximating the cone of copositive kernels to estimate the stability number of infinite graphsScaling relationship between the copositive cone and Parrilo's first level approximationThe boosted DC algorithm for linearly constrained DC programmingInteriors of completely positive conesSeparating doubly nonnegative and completely positive matricesSeparation and relaxation for cones of quadratic formsCopositive optimization -- recent developments and applicationsThink co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimizationAn improved algorithm to test copositivityAn algorithm for determining copositive matricesCopositivity detection by difference-of-convex decomposition and \(\omega \)-subdivisionCompletely positive and completely positive semidefinite tensor relaxations for polynomial optimizationCopositive programming via semi-infinite optimizationFactorization and cutting planes for completely positive matrices by copositive projectionConvex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximationOn the computational complexity of membership problems for the completely positive cone and its dualNew approximations for the cone of copositive matrices and its dualNew and old bounds for standard quadratic optimization: dominance, equivalence and incomparabilityTesting copositivity via mixed-integer linear programmingHandelman's hierarchy for the maximum stable set problemCopositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017Exploiting equalities in polynomial programmingThe \(\mathcal A\)-truncated \(K\)-moment problemAnalysis of copositive optimization based linear programming bounds on standard quadratic optimizationEffective Pólya semi-positivity for non-negative polynomials on the simplexLovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphsAn axiomatic duality framework for the theta body and related convex cornersLinear conic formulations for two-party correlations and values of nonlocal gamesOptimization over structured subsets of positive semidefinite matrices via column generationA robust Lagrangian-DNN method for a class of quadratic optimization problemsAlgorithmic copositivity detection by simplicial partitionEquivalences and differences in conic relaxations of combinatorial quadratic optimization problemsStability of polytopes of matrices via affine parameter-dependent Lyapunov functions: asymptotically exact LMI conditionsQuadratic factorization heuristics for copositive programmingOptimizing a polyhedral-semidefinite relaxation of completely positive programsA completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxationPólya's theorem with zerosA characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programmingA Comprehensive Analysis of Polyhedral Lift-and-Project MethodsPolyhedral approximations of the semidefinite cone and their applicationA MAX-CUT formulation of 0/1 programsAlternative SDP and SOCP approximations for polynomial optimizationCopositive ProgrammingSimple ingredients leading to very efficient heuristics for the maximum clique problemLower bounds on nonnegative rank via nonnegative nuclear normsInner approximating the completely positive cone via the cone of scaled diagonally dominant matricesOn the polyhedral lift-and-project methods and the fractional stable set polytopeSearching for critical angles in a convex coneA quantitative Pólya's theorem with zerosAn alternative perspective on copositive and convex relaxations of nonconvex quadratic programsOn the \(k\)-independence number of graphsComplexity aspects of local minima and related notionsLower bounds on matrix factorization ranks via noncommutative polynomial optimizationOn upper bounding Shannon capacity of graph through generalized conic programmingOn the complexity of finding a local minimizer of a quadratic function over a polytopeContinuous cubic formulations for cluster detection problems in networksOn an extension of Pólya's PositivstellensatzD.C. versus copositive bounds for standard QPCompletely positive reformulations for polynomial optimizationExploiting symmetry in copositive programs via semidefinite hierarchiesA note on completely positive relaxations of quadratic problems in a multiobjective frameworkDetecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation schemeA dynamic inequality generation scheme for polynomial programmingA Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems







This page was built for publication: Approximation of the Stability Number of a Graph via Copositive Programming