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 (4)

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

This page was built for publication: Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope