@inbook{fe17af142f8848e58a8a46421584369c,

title = "Computing the Edge Expansion of a Graph Using Semidefinite Programming",

abstract = "Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two versions of an exact algorithm using semidefi- nite programming (SDP) to compute this constant for any graph. The SDP relaxation is used to first reduce the search space considerably. One version applies then an SDP-based branch-and-bound algorithm, along with heuristic search. The other version transforms the problem into an instance of a max-cut problem and solves this using a state-of-the-art solver. Numerical results demonstrate that we clearly outperform mixed- integer quadratic solvers as well as another SDP-based algorithm from the literature.",

author = "Akshay Gupte and Melanie Siebenhofer and Angelika Wiegele",

year = "2024",

month = may,

day = "22",

doi = "10.1007/978-3-031-60924-4_9",

language = "English",

volume = "14594",

series = "LNCS - Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "111 -- 124",

editor = "Amitabh Basu and Mahjoub, {Ali Ridha} and {Salazar Gonz{\'a}lez}, {Juan Jos{\'e}}",

booktitle = "Combinatorial Optimization",

}