SDP relaxations for some combinatorial optimization problems
From MaRDI portal
Publication:2802546
DOI10.1007/978-1-4614-0769-0_27zbMATH Open1334.90116OpenAlexW2124892043MaRDI QIDQ2802546FDOQ2802546
Authors: Renata Sotirov 
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
Recommendations
- On Semidefinite Programming Relaxations of the Traveling Salesman Problem
- On semidefinite programming relaxations of maximum \(k\)-section
- Relaxations of combinatorial problems via association schemes
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Semidefinite programming (90C22) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Cites Work
- QAPLIB - a quadratic assignment problem library
- An Efficient Heuristic Procedure for Partitioning Graphs
- Assignment Problems
- Interlacing eigenvalues and graphs
- Solution of a Large-Scale Traveling-Salesman Problem
- The quadratic assignment problem. Theory and algorithms
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Optimal Assignments of Numbers to Vertices
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- Some simplified NP-complete graph problems
- Title not available (Why is that?)
- The NP-completeness of the bandwidth minimization problem
- Semidefinite programming relaxations for the quadratic assignment problem
- On semidefinite programming relaxations of maximum \(k\)-section
- A comparison of the Delsarte and Lovász bounds
- On the Sum of the Largest Eigenvalues of a Symmetric Matrix
- Title not available (Why is that?)
- Laplace eigenvalues and bandwidth‐type invariants of graphs
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
- Title not available (Why is that?)
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- Lower Bounds for the Partitioning of Graphs
- Recent advances in the solution of quadratic assignment problems
- The quadratic assignment problem
- On equivalence of semidefinite relaxations for quadratic matrix programming
- A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
- Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Solving large quadratic assignment problems on computational grids
- The Backboard Wiring Problem: A Placement Algorithm
- Hospital Layout as a Quadratic Assignment Problem
- Title not available (Why is that?)
- A spectral approach to bandwidth and separator problems in graphs
- A Copositive Programming Approach to Graph Partitioning
- Graph partitioning using linear and semidefinite programming
- Semidefinite programming relaxations for the graph partitioning problem
- Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
- The bandwidth problem for graphs and matrices—a survey
- On Semidefinite Programming Relaxations of the Traveling Salesman Problem
- On Lagrangian relaxation of quadratic matrix constraints
- Solving quadratic assignment problems using convex quadratic programming relaxations
- A new bound for the quadratic assignment problem based on convex quadratic programming
- A projection technique for partitioning the nodes of a graph
- A comparison of lower bounds for the symmetric circulant traveling salesman problem
- Bounds for the quadratic assignment problem using the bundle method
- Title not available (Why is that?)
- A Near-Maximum-Likelihood Decoding Algorithm for MIMO Systems Based on Semi-Definite Programming
- Title not available (Why is that?)
- Graph partitioning and parallel computing
- Matrix-Lifting Semi-Definite Programming for Detection in Multiple Antenna Systems
Cited In (24)
- A framework for solving mixed-integer semidefinite programs
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods
- Relaxations of combinatorial problems via association schemes
- Graph bisection revisited
- Restarting after branching in the SDP approach to MAX-CUT and similar combinatorial optimization problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- On conic QPCCs, conic QCQPs and completely positive programs
- SDP-based bounds for graph partition via extended ADMM
- Semidefinite programming for discrete optimization and matrix completion problems
- Combinatorial optimization problems in engineering applications
- A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
- Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems
- Matrix relaxations in combinatorial optimization
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- Certifiably optimal sparse inverse covariance estimation
- Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
- On semidefinite programming bounds for graph bandwidth
- Semidefinite and Lagrangian relaxations for hard combinatorial problems
- An efficient semidefinite programming relaxation for the graph partition problem
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables
- Partitioning through projections: strong SDP bounds for large graph partition problems
Uses Software
This page was built for publication: SDP relaxations for some combinatorial optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802546)
