Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope

DOI10.1016/j.jctb.2014.02.011zbMath1297.05167arXiv1205.2040OpenAlexW2129434754MaRDI QIDQ740647

Marianna. E.-Nagy, Monique Laurent, Antonios Varvitsiotis

Publication date: 4 September 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.2040

zbMATH Keywords

semidefinite programmingmatrix completiongraph minorcorrelation matrixtree-widthGrothendieck constantgram representation

Mathematics Subject Classification ID

Semidefinite programming (90C22) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Graph cores via universal completability, Matrices with high completely positive semidefinite rank, Positive semidefinite matrix completion, universal rigidity and the strong Arnold property, Unavoidable minors for graphs with large \(\ell_p\)-dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The real positive semidefinite completion problem for series-parallel graphs
• Two tree-width-like graph invariants
• Graph minors. XX: Wagner's conjecture
• Realizability of graphs
• Realizability of graphs in three dimensions
• Geometric algorithms and combinatorial optimization
• Multiplicities of eigenvalues and tree-width of graphs
• Positive semidefinite matrix completion, universal rigidity and the strong Arnold property
• Semidefinite programming relaxations and algebraic optimization in control
• Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint
• Near-optimal algorithms for unique games
• Approximation Algorithms and Semidefinite Programming
• On the Shannon capacity of a graph
• A Note on Extreme Correlation Matrices
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the Facial Structure of the Set of Correlation Matrices
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Quadratic forms on graphs
• Geometry of cuts and metrics
• Spectral characterization of tree-width-two graphs
• Tree width and regular triangulations