An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

DOI10.1007/s11425-014-4900-5zbMath1335.49053MaRDI QIDQ2018887

Xiaoyan Zhang, Xingxing Yu, Zan-Bo Zhang, Bao-Gang Xu

Publication date: 26 March 2015

Published in: Science China. Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11425-014-4900-5

zbMATH Keywords

semidefinite programming; combinatorial optimization; relaxation; performance ratio; randomized approximation algorithm; limited unbalance; max hypergraph cut

Mathematics Subject Classification ID

90C22: Semidefinite programming

49M37: Numerical methods based on nonlinear programming

90C27: Combinatorial optimization

68W20: Randomized algorithms

Related Items

A bound on judicious bipartitions of directed graphs

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
• New semidefinite programming relaxations for box constrained quadratic program
• On judicious bisections of graphs
• Approximation algorithms for indefinite complex quadratic maximization problems
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• A note on balanced bipartitions
• Improved approximation algorithms for maximum graph partitioning problems
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• The hardness of approximation: Gap location
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• A note on approximating Max-Bisection on regular graphs
• An improved rounding method and semidefinite programming relaxation for graph partition
• Improved approximations for max set splitting and max NAE SAT
• Inapproximability results for set splitting and satisfiability problems with no mixed clauses
• Approximation algorithms for maximum cut with limited unbalance
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Outward rotations
• Improved approximation of Max-Cut on graphs of bounded degree
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Judicious partitions of bounded‐degree graphs
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• Problems and results on judicious partitions
• Balanced judicious bipartitions of graphs
• Some optimal inapproximability results
• The RPR2 rounding technique for semidefinite programs
• Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
• A .699-approximation algorithm for Max-Bisection.
• Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability
• Non-oblivious local search for graph and hypergraph coloring problems