scientific article; zbMATH DE number 5165614
From MaRDI portal
Publication:5292090
zbMath1194.90066MaRDI QIDQ5292090
Publication date: 19 June 2007
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
max-cut problemmaximum stable set problemLovász theta numberGoemans-Williamson approximation algorithm
Related Items (48)
Beating the SDP bound for the floor layout problem: a simple combinatorial idea ⋮ Matrix Relaxations in Combinatorial Optimization ⋮ Tightening a copositive relaxation for standard quadratic optimization problems ⋮ Sparse noncommutative polynomial optimization ⋮ Copositive programming motivated bounds on the stability and the chromatic numbers ⋮ Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ Generating cutting planes for the semidefinite relaxation of quadratic programs ⋮ RLT-POS: reformulation-linearization technique-based optimization software for solving polynomial programming problems ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ Semidefinite programming relaxations for graph coloring and maximal clique problems ⋮ Stochastic nuclear outages semidefinite relaxations ⋮ Semidefinite bounds for the stability number of a graph via sums of squares of polynomials ⋮ A new approximation hierarchy for polynomial conic optimization ⋮ Binary Positive Semidefinite Matrices and Associated Integer Polytopes ⋮ On Integrality in Semidefinite Programming for Discrete Optimization ⋮ Optimal Learning in Linear Regression with Combinatorial Feature Selection ⋮ Copositive optimization -- recent developments and applications ⋮ A simplified treatment of Ramana's exact dual for semidefinite programming ⋮ Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization ⋮ A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs ⋮ Enhancing RLT-based relaxations for polynomial programming problems via a new class of \(v\)-semidefinite cuts ⋮ Semidefinite resolution and exactness of semidefinite relaxations for satisfiability ⋮ Binary positive semidefinite matrices and associated integer polytopes ⋮ A guide to conic optimisation and its applications ⋮ Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques ⋮ An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming ⋮ Exactness criteria for SDP-relaxations of quadratic extremum problems ⋮ On reduction of duality gap in quadratic knapsack problems ⋮ Finding the Largest Low-Rank Clusters With Ky Fan $2$-$k$-Norm and $\ell_1$-Norm ⋮ A convex optimisation framework for the unequal-areas facility layout problem ⋮ New quadratic models for the maximum weighted cut problem ⋮ Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem ⋮ Semidefinite programming relaxations and algebraic optimization in control ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Block-diagonal semidefinite programming hierarchies for 0/1 programming ⋮ Introduction to Semidefinite, Conic and Polynomial Optimization ⋮ Convex Hulls of Algebraic Sets ⋮ Relaxations of Combinatorial Problems Via Association Schemes ⋮ Semidefinite Programming and Constraint Programming ⋮ Computational Approaches to Max-Cut ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Faster, but weaker, relaxations for quadratically constrained quadratic programs ⋮ Rank Optimality for the Burer--Monteiro Factorization ⋮ An approximation algorithm for the maximum spectral subgraph problem ⋮ A semidefinite optimization approach for the single-row layout problem with unequal dimensions ⋮ On Polyhedral Approximations of the Positive Semidefinite Cone ⋮ Primal-dual Newton method with steepest descent for the linear semidefinite programming problem: Newton's system of equations
This page was built for publication:
