20 citations · 28 across the 6 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…
An SDP-Based Approach for Computing the Stability Number of a Graph
Elisabeth Gaar, Melanie Siebenhofer, Angelika Wiegele
Finding the stability number of a graph, i.e., the maximum number of vertices of which no two are adjacent, is a well known NP-hard combinatorial optimization problem. Since this p…
BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints
Nicolò Gusmeroli, Timotej Hrga, Borut Lužar +3
We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original…