3 papers
math.OC2025
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…
math.OC2025
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…
math.OC2024
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…