Semidefinite programming and combinatorial optimization
From MaRDI portal
Publication:5906394
DOI10.1016/S0168-9274(98)00097-XzbMath0956.90030OpenAlexW2082156532MaRDI QIDQ5906394
Publication date: 18 March 2001
Published in: Applied Numerical Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0168-9274(98)00097-x
semidefinite programmingcombinatorial optimizationinteger programslinear programs over conesnonliner relaxations
Related Items
SDP-based bounds for graph partition via extended ADMM, Approximation algorithm for MAX DICUT with given sizes of parts, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Solving graph equipartition SDPs on an algebraic variety, Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation, Semidefinite programming for discrete optimization and matrix completion problems, Semi-definite relaxation algorithm of multiple knapsack problem, Semidefinite spectral clustering, A novel formulation of the max-cut problem and related algorithm, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
Uses Software
Cites Work
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Least squares with a quadratic constraint
- Some applications of optimization in matrix theory
- The hypermetric cone is polyhedral
- Laplacian eigenvalues and the maximum cut problem
- Node and edge relaxations of the max-cut problem
- A computational study of graph partitioning
- Semidefinite programming in combinatorial optimization
- Exploiting sparsity in primal-dual interior-point methods for semidefinite programming
- Connection between semidefinite relaxations of the max-cut and stable set problems
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- Approximating the independence number via the \(\vartheta\)-function
- A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
- Solving the max-cut problem using eigenvalues
- A projection technique for partitioning the nodes of a graph
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- A spectral technique for coloring random 3-colorable graphs (preliminary version)
- Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
- The Gauss-Newton direction in semidefinite programming
- On the Sum of the Largest Eigenvalues of a Symmetric Matrix
- Large-Scale Optimization of Eigenvalues
- On the Shannon capacity of a graph
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- On the Nesterov--Todd Direction in Semidefinite Programming
- Linear Matrix Inequalities in System and Control Theory
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Primal--Dual Path-Following Algorithms for Semidefinite Programming
- Primal-Dual Interior-Point Methods for Self-Scaled Cones
- On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
- A Spectral Bundle Method for Semidefinite Programming
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- Convex Relaxations of (0, 1)-Quadratic Programming
- Semidefinite Programming
- An Interior-Point Method for Semidefinite Programming
- Combining semidefinite and polyhedral relaxations for integer programs
- Duality and asymptotic solvability over cones
- Some convexity theorems for matrices
- Lower Bounds for the Partitioning of Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
