Semidefinite programming based algorithms for the sparsest cut problem

DOI10.1051/RO/2011104MaRDI QIDQ4917216zbMATH OpenOpenAlexFDO

Authors Luis A. A. Meira, Flávio K. Miyazawa

Publication date 29 April 2013

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ro/2011104

zbMATH Keywords

combinatoricssemidefinite programmingsparsest cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Semidefinite programming (90C22)

Recommendations

• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization

Cited in

(4)

• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• Computing the edge expansion of a graph using semidefinite programming
• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion

Describes a project that uses

Uses Software

• SDPA

This page was built for publication: Semidefinite programming based algorithms for the sparsest cut problem

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