4 papers
Improved Lower Bounds for Global Polynomial Optimisation
Henning Seidler
We present a branch-and-bound algorithm to improve the lower bounds obtained by SONC/SAGE. The running time is fixed-parameter tractable in the number of variables. Furthermore, we…
Exact Optimization via Sums of Nonnegative Circuits and Sums of AM/GM Exponentials
Victor Magron, Henning Seidler, Timo de Wolff
We provide two hybrid numeric-symbolic optimization algorithms, computing exact sums of nonnegative circuits (SONC) and sums of arithmetic-geometric-exponentials (SAGE) decompositi…
An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization
Henning Seidler, Timo de Wolff
Finding the minimum of a multivariate real polynomial is a well-known hard problem with various applications. We present a polynomial time algorithm to approximate such lower bound…
The Minimum Shared Edges Problem on Grid-like Graphs
Till Fluschnik, Meike Hatzel, Steffen Härtlein +2
We study the NP-hard Minimum Shared Edges (MSE) problem on graphs: decide whether it is possible to route paths from a start vertex to a target vertex in a given graph while us…