Matrix Relaxations in Combinatorial Optimization
From MaRDI portal
Publication:2897308
DOI10.1007/978-1-4614-1927-3_17zbMath1242.90201OpenAlexW79937293MaRDI QIDQ2897308
Publication date: 10 July 2012
Published in: Mixed Integer Nonlinear Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-1-4614-1927-3_17
Related Items
Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem, SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY, Improving ADMMs for solving doubly nonnegative programs through dual factorization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Copositive programming motivated bounds on the stability and the chromatic numbers
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- A boundary point method to solve semidefinite programs
- On the solution of large-scale SDP problems by the modified barrier method using iterative solvers
- Geometric algorithms and combinatorial optimization
- The NP-completeness of the bandwidth minimization problem
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Semidefinite programming in combinatorial optimization
- Graph partitioning using linear and semidefinite programming
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Numerical evaluation of SBmethod
- Aspects of semidefinite programming. Interior point algorithms and selected applications
- Semidefinite programming
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
- Approximation of the Stability Number of a Graph via Copositive Programming
- New approximation guarantee for chromatic number
- A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
- A Variational Approach to Copositive Matrices
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- Assignment Problems
- Semidefinite Relaxations for Integer Programming
- The Operator $\Psi$ for the Chromatic Number of a Graph
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
- An Augmented Primal-Dual Method for Linear Conic Programs
- Improving the performance guarantee for approximate graph coloring
- Some NP-complete problems in quadratic and nonlinear programming
- Approximate graph coloring by semidefinite programming
- A comparison of the Delsarte and Lovász bounds
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Complexity Results for Bandwidth Minimization
- On the Shannon capacity of a graph
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A study of search directions in primal-dual interior-point methods for semidefinite programming
- A Spectral Bundle Method for Semidefinite Programming
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- Fastest Mixing Markov Chain on a Graph
- A spectral approach to bandwidth and separator problems in graphs
- Semidefinite Programming
- Regularization Methods for Semidefinite Programming
- Maxima for Graphs and a New Proof of a Theorem of Turán
- A Copositive Programming Approach to Graph Partitioning
- Handbook of semidefinite programming. Theory, algorithms, and applications
- On copositive programming and standard quadratic optimization problems
- On the hardness of approximating the chromatic number