SDP Relaxations for Some Combinatorial Optimization Problems
From MaRDI portal
Publication:2802546
DOI10.1007/978-1-4614-0769-0_27zbMath1334.90116OpenAlexW2124892043MaRDI QIDQ2802546
Publication date: 26 April 2016
Published in: International Series in Operations Research & Management Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-1-4614-0769-0_27
Semidefinite programming (90C22) Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items (14)
SDP-based bounds for graph partition via extended ADMM ⋮ Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems ⋮ On conic QPCCs, conic QCQPs and completely positive programs ⋮ On semidefinite programming bounds for graph bandwidth ⋮ Graph bisection revisited ⋮ Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods ⋮ Partitioning through projections: strong SDP bounds for large graph partition problems ⋮ An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem ⋮ Certifiably optimal sparse inverse covariance estimation ⋮ A framework for solving mixed-integer semidefinite programs ⋮ A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems ⋮ Semidefinite programming and eigenvalue bounds for the graph partition problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
- A comparison of lower bounds for the symmetric circulant traveling salesman problem
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- Bounds for the quadratic assignment problem using the bundle method
- The NP-completeness of the bandwidth minimization problem
- Some simplified NP-complete graph problems
- QAPLIB - a quadratic assignment problem library
- The quadratic assignment problem. Theory and algorithms
- Semidefinite programming relaxations for the quadratic assignment problem
- Recent advances in the solution of quadratic assignment problems
- Graph partitioning using linear and semidefinite programming
- Graph partitioning and parallel computing
- Solving large quadratic assignment problems on computational grids
- Interlacing eigenvalues and graphs
- A projection technique for partitioning the nodes of a graph
- On semidefinite programming relaxations of maximum \(k\)-section
- Semidefinite programming relaxations for the graph partitioning problem
- On Lagrangian Relaxation of Quadratic Matrix Constraints
- Solving quadratic assignment problems using convex quadratic programming relaxations
- The Quadratic Assignment Problem
- On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming
- The Backboard Wiring Problem: A Placement Algorithm
- Assignment Problems
- A Near-Maximum-Likelihood Decoding Algorithm for MIMO Systems Based on Semi-Definite Programming
- On Semidefinite Programming Relaxations of the Traveling Salesman Problem
- A comparison of the Delsarte and Lovász bounds
- The bandwidth problem for graphs and matrices—a survey
- On the Sum of the Largest Eigenvalues of a Symmetric Matrix
- Cones of Matrices and Set-Functions and 0–1 Optimization
- An Efficient Heuristic Procedure for Partitioning Graphs
- Hospital Layout as a Quadratic Assignment Problem
- Laplace eigenvalues and bandwidth‐type invariants of graphs
- A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
- Matrix-Lifting Semi-Definite Programming for Detection in Multiple Antenna Systems
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- A spectral approach to bandwidth and separator problems in graphs
- Solution of a Large-Scale Traveling-Salesman Problem
- A Copositive Programming Approach to Graph Partitioning
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
- Optimal Assignments of Numbers to Vertices
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Lower Bounds for the Partitioning of Graphs
- Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
- Handbook of semidefinite programming. Theory, algorithms, and applications
- A new bound for the quadratic assignment problem based on convex quadratic programming
This page was built for publication: SDP Relaxations for Some Combinatorial Optimization Problems
