A semidefinite programming approach to the hypergraph minimum bisection problem

DOI10.1080/02331930903233744MaRDI QIDQ2996813zbMATH OpenOpenAlexFDO

Authors Changhui Choi, Samuel Burer

Publication date 3 May 2011

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331930903233744

zbMATH Keywords

semidefinite programmingdigital circuit designhypergraph minimum bisection

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Semidefinite programming (90C22) Applications of graph theory to circuits and networks (94C15)

Recommendations

• scientific article; zbMATH DE number 5237020
• Graph bisection revisited
• Solving Graph Bisection Problems with Semidefinite Programming
• Solution of one problem of optimal partition of the vertex set of a hypergraph
• scientific article; zbMATH DE number 5117494

Cites work

• A fast and robust network bisection algorithm
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• A polylogarithmic approximation of the minimum bisection
• Approximation of dense-n/2-subgraph and the complement of min-bisection
• Computational enhancements in low-rank semidefinite programming
• Expander flows, geometric embeddings and graph partitioning
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Modeling hypergraphs by graphs with the same mincut properties
• Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
• Recent directions in netlist partitioning: a survey
• Some simplified NP-complete graph problems

Cited in

(6)

• On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets
• Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
• scientific article; zbMATH DE number 5237020 (Why is no real title available?)
• Minimum transversals of maximum matchings as approximate solutions to the bisection problem
• Semidefinite programming based approaches to the break minimization problem
• An Improved Semidefinite Programming Hierarchies Rounding Approximation Algorithm for Maximum Graph Bisection Problems

This page was built for publication: A semidefinite programming approach to the hypergraph minimum bisection problem

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