Christoph Helmberg We study the problem of maximizing the second smallest eigenvalue of the Laplace matrix of a graph over all nonnegative edge weightings with bounded total weight. The optimal value is the \emph{absolute algebraic connectivity} introduced by Fiedler, who proved tight connections of this value to the connectivity of the graph. Using semidefinite programming techniques and … Read more
For a real world problem — transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand — we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost … Read more
The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges … Read more