Ellipsoidal relaxations of the stable set problem: theory and algorithms
From MaRDI portal
Recommendations
- A new approach to the stable set problem based on ellipsoids
- Computational Experience with Stable Set Relaxations
- A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
- Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
- Strengthening Chvátal-Gomory cuts for the stable set problem
Cites work
- A branch and cut solver for the maximum stable set problem
- A branch-and-cut algorithm for the maximum cardinality stable set problem
- A comparison of the Delsarte and Lovász bounds
- A Convex Quadratic Characterization of the Lovász Theta Number
- A new approach to the stable set problem based on ellipsoids
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- An application of the Lovász-Schrijver M(K, K) operator to the stable set problem
- Applications of second-order cone programming
- Benchmarking optimization software with performance profiles.
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Computational Experience with Stable Set Relaxations
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Exploring the relationship between max-cut and stable set relaxations
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 4070633 (Why is no real title available?)
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 1947416 (Why is no real title available?)
- scientific article; zbMATH DE number 956840 (Why is no real title available?)
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
- On Polyhedral Approximations of the Second-Order Cone
- On the facial structure of set packing polyhedra
- On the Shannon capacity of a graph
- On the Slater condition for the SDP relaxations of nonconvex sets
- Reducibility among combinatorial problems
- Second-order cone programming
- Semidefinite programming relaxation for nonconvex quadratic programs
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- Strong lift-and-project cutting planes for the stable set problem
- The Cutting-Plane Method for Solving Convex Programs
- Using constraint programming to solve the maximum clique problem
Cited in
(9)- A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
- Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
- The stable set problem: clique and nodal inequalities revisited
- Strengthening Chvátal-Gomory cuts for the stable set problem
- A new approach to the stable set problem based on ellipsoids
- Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
- Projective cutting-planes
- Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems
- Application of the Lovász-Schrijver operator to compact stable set integer programs
This page was built for publication: Ellipsoidal relaxations of the stable set problem: theory and algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2949518)
