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

DOI10.1007/s11425-014-4900-5zbMath1335.49053OpenAlexW2001501791MaRDI 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 programmingcombinatorial optimizationrelaxationperformance ratiorandomized approximation algorithmlimited unbalancemax hypergraph cut

Mathematics Subject Classification ID

Semidefinite programming (90C22) Numerical methods based on nonlinear programming (49M37) Combinatorial optimization (90C27) Randomized algorithms (68W20)

Related Items (2)

A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis ⋮ 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

This page was built for publication: An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance