Approximations of convex bodies by polytopes and by projections of spectrahedra [PDF]
, 2012 We prove that for any compact set B in R^d and for any epsilon >0 there is a finite subset X of B of |X|=d^{O(1/epsilon^2)} points such that the maximum absolute value of any linear function ell: R^d --> R on X approximates the maximum absolute value of ...
Barvinok, Alexander
core +1 more source
Exposed faces of semidefinitely representable sets
, 2009 A linear matrix inequality (LMI) is a condition stating that a symmetric matrix whose entries are affine linear combinations of variables is positive semidefinite.
Netzer, Tim +2 more
core +1 more source
Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix [PDF]
, 2013 The positive semidefinite rank of a nonnegative $(m\times n)$-matrix~$S$ is the minimum number~$q$ such that there exist positive semidefinite $(q\times q)$-matrices $A_1,\dots,A_m$, $B_1,\dots,B_n$ such that $S(k,\ell) = \mbox{tr}(A_k^* B_\ell)$.
Dirk, Oliver Theis, Troy Lee
core
Exploiting Group Symmetry in Truss Topology Optimization [PDF]
AMS classification: 90C22, 20Cxx, 70-08truss topology optimization;semidefinite programming;group ...
Bai, Y.Q. +3 more
core +1 more source
Improved bounds for the crossing numbers of K_m,n and K_n
, 2004 It has been long--conjectured that the crossing number cr(K_m,n) of the complete bipartite graph K_m,n equals the Zarankiewicz Number Z(m,n):= floor((m-1)/2) floor(m/2) floor((n-1)/2) floor(n/2). Another long--standing conjecture states that the crossing
de Klerk, E. +4 more
core +2 more sources
On Semidefinite Programming Relaxations of the Travelling Salesman Problem (Replaced by DP 2008-96) [PDF]
AMS classification: 90C22, 20Cxx, 70-08traveling salesman problem;semidefinite programming;quadratic as- signment ...
Klerk, E. de +2 more
core +1 more source
On Semidefinite Programming Relaxations of Association Schemes With Application to Combinatorial Optimization Problems [PDF]
AMS classification: 90C22, 20Cxx, 70-08traveling salesman problem;maximum bisection;semidefinite programming;association ...
Klerk, E. de, Pasechnik, D.V.
core +1 more source
Deciding polyhedrality of spectrahedra
, 2015 Spectrahedra are linear sections of the cone of positive semidefinite matrices that, as convex bodies, generalize the class of polyhedra. In this paper we investigate the problem of recognizing when a spectrahedron is polyhedral.
Bhardwaj, Avinash +2 more
core +1 more source
On the Lovasz O-number of Almost Regular Graphs With Application to Erdos-Renyi Graphs [PDF]
AMS classifications: 05C69; 90C35; 90C22;Erdos-Renyi graph;stability number;Lovasz O-number;Schrijver O-number;C*-algebra;semidefinite ...
Klerk, E. de +3 more
core +1 more source
Exploiting Group Symmetry in Semidefinite Programming Relaxations of the Quadratic Assignment Problem [PDF]
We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment ...
Klerk, E. de, Sotirov, R.
core +1 more source