4 papers
The Augmented Mixing Method: Computing High-Accuracy Primal-Dual Solutions to Large-Scale SDPs via Column Updates
Daniel Brosch, Jan Schwiddessen, Angelika Wiegele
The Burer-Monteiro factorization has become a powerful tool for solving large-scale semidefinite programs (SDPs), enabling recently developed low-rank solvers to tackle problems pr…
Edge expansion of a graph: SDP-based computational strategies
Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele
Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms u…
Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem
Frank de Meijer, Melanie Siebenhofer, Renata Sotirov +1
In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We present a formulation…
Connectivity via convexity: Bounds on the edge expansion in graphs
Timotej Hrga, Melanie Siebenhofer, Angelika Wiegele
Convexification techniques have gained increasing interest over the past decades. In this work, we apply a recently developed convexification technique for fractional programs by H…