We study the computational complexity of finding extremal principal minors of a positive definite matrix. In particular, we focus on the NP-hard problem of maximizing the determinant over the set of principal submatrices of a given order. This problem arises in the area of statistical design,...

The boolean quadric polytope Pn is the convex hull in d:= (n;l) dimensions of the binary solutions of XiXj = Yij, for all i j in N := {l, 2, ... , n} (n ~ 2). The polytope is naturally modeled by a somewhat larger polytope; namely, Qn the solution set of Yij :5 Xi, Yij :5 Xj, X, + Xj :5 1 + Yij,...

We demonstrate that two key theorems of Amaldi et al. (Math Methods Oper Res 69:205–223, 2009 ), which they presented with rather complicated proofs, can be more easily and cleanly established using a simple and classical property of binary matroids. Besides a simpler proof, we see that both...

We describe a branch-and-bound (b&b) method aimed at searching for an exact solution of the fundamental problem of decomposing a matrix into the sum of a sparse matrix and a low-rank matrix. Previous heuristic techniques employed convex and nonconvex optimization. We leverage and extend those...

We demonstrate that two key theorems of Amaldi et al. (Math Methods Oper Res 69:205–223, <CitationRef CitationID="CR1">2009</CitationRef>), which they presented with rather complicated proofs, can be more easily and cleanly established using a simple and classical property of binary matroids. Besides a simpler proof, we see that both...</citationref>