A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis

DOI10.1007/S10898-022-01183-7MaRDI QIDQ6064054zbMATH OpenOpenAlexFDO

Authors

Publication date 8 November 2023

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-022-01183-7

zbMATH Keywords

approximation algorithmcomplex semidefinite programmingmax hypergraph 3-cutrandomized algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Semidefinite programming (90C22) Combinatorial optimization (90C27)

Recommendations

• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• scientific article; zbMATH DE number 1670644
• Approximation algorithms for maximum cut with limited unbalance
• Approximating Maximum Cut with Limited Unbalance
• An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding

Cites work

• A .699-approximation algorithm for Max-Bisection.
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• Algorithms – ESA 2005
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Approximation algorithms for indefinite complex quadratic maximization problems
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Approximation algorithms for maximum cut with limited unbalance
• Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
• Better balance by being biased: a 0.8776-approximation for {\textsc{Max Bisection}}
• scientific article; zbMATH DE number 1304324 (Why is no real title available?)
• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved approximations for max set splitting and max NAE SAT
• New semidefinite programming relaxations for box constrained quadratic program
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• P-Complete Approximation Problems
• Semidefinite approximation for mixed binary quadratically constrained quadratic programs
• The RPR2 rounding technique for semidefinite programs
• Tightness of a New and Enhanced Semidefinite Relaxation for MIMO Detection

Cited in

(3)

• A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem
• An improved approximation algorithm for hypergraph max p-section
• An improved SDP rounding approximation algorithm for the max hypergraph bisection

This page was built for publication: A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis

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