A new graph parameter related to bounded rank positive semidefinite matrix completions

DOI10.1007/s10107-013-0648-xzbMath1293.05238arXiv1204.0734OpenAlexW2024448984MaRDI QIDQ2248754

Antonios Varvitsiotis, Monique Laurent

Publication date: 27 June 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingmatrix completiongraph minorEuclidean distance matrixcombinatorial matrix theorygraph realizabilitygeometric graph representation

Mathematics Subject Classification ID

Semidefinite programming (90C22) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph minors (05C83) Graph representations (geometric and intersection representations, etc.) (05C62) Matrix completion problems (15A83)

Related Items

Sums of squares and quadratic persistence on real projective varieties, Graph cores via universal completability, Universal completability, least eigenvalue frameworks, and vector colorings, Do Sums of Squares Dream of Free Resolutions?, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem, Typical ranks in symmetric matrix completion, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Unavoidable minors for graphs with large \(\ell_p\)-dimension, Determinantal sampling designs, Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint, Selected Open Problems in Discrete Geometry and Optimization, Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

Uses Software

• Max-AO

Cites Work

• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian
• The real positive semidefinite completion problem for series-parallel graphs
• Two tree-width-like graph invariants
• Graph minors. XX: Wagner's conjecture
• Euclidean distance matrices, semidefinite programming and sensor network localization
• Positive definite completions of partial Hermitian matrices
• Sum of squares method for sensor network localization
• Realizability of graphs
• Realizability of graphs in three dimensions
• Forbidden minors characterization of partial 3-trees
• Orthogonal representations, minimum rank, and graph complements
• The minimum rank of symmetric matrices described by a graph: a survey
• Solving Euclidean distance matrix completion problems via semidefinite progrmming
• The real positive definite completion problem for a simple cycle
• Maximum stable set formulations and heuristics based on continuous optimization
• Multiplicities of eigenvalues and tree-width of graphs
• A remark on the rank of positive semidefinite matrices subject to affine constraints
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• Topology of series-parallel networks
• Polynomial Instances of the Positive Semidefinite and Euclidean Distance Matrix Completion Problems
• Euclidean Distance Matrices and Applications
• Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint
• The Gram Dimension of a Graph
• The rotational dimension of a graph
• A semidefinite programming approach to tensegrity theory and realizability of graphs
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Embedded in the Shadow of the Separator
• Matrix Analysis
• On the Shannon capacity of a graph
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Convex Analysis
• Geometry of cuts and metrics