Edge expansion of a graph: SDP-based computational strategies

DOI10.1007/S12532-025-00297-9MaRDI QIDQ7312748zbMATH OpenFDO

Authors Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele

Publication date 12 August 2026

Published in Mathematical Programming Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S12532-025-00297-9

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Fractional programming (90C32) Programming involving graphs or networks (90C35)

Cites work

• \texttt{EXPEDIS}: an exact penalty method over discrete sets
• A thermodynamically motivated simulation procedure for combinatorial optimization problems
• Basic Facts about Expander Graphs
• BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
• BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems
• Expander flows, geometric embeddings and graph partitioning
• Expander graphs and their applications
• Expansion of random 0/1 polytopes
• Experiments in quadratic 0-1 programming
• Fractional Programming. II, On Dinkelbach's Algorithm
• Graph expansion and the unique games conjecture
• Graph Partitioning and Graph Clustering
• scientific article; zbMATH DE number 1182569 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 2115090 (Why is no real title available?)
• scientific article; zbMATH DE number 2196285 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Julia: a fresh approach to numerical computing
• JuMP 1.0: recent improvements to a modeling language for mathematical optimization
• Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On Dantzig figures from graded lexicographic orders
• On Nonlinear Fractional Programming
• On semidefinite programming relaxations of maximum \(k\)-section
• On the expansion of combinatorial polytopes
• Partitioning through projections: strong SDP bounds for large graph partition problems
• SDP-based bounds for graph partition via extended ADMM
• Semidefinite programming based algorithms for the sparsest cut problem
• Semidefinite programming relaxations for the graph partitioning problem
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Some simplified NP-complete graph problems
• Submodularity in Conic Quadratic Mixed 0–1 Optimization
• Testing the expansion of a graph
• The Boolean quadratic polytope: Some characteristics, facets and relatives

This page was built for publication: Edge expansion of a graph: SDP-based computational strategies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7312748)