An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
DOI10.1007/S11425-014-4900-5zbMATH Open1335.49053OpenAlexW2001501791MaRDI QIDQ2018887FDOQ2018887
Authors: Xingxing Yu, Xiaoyan Zhang, Zan-Bo Zhang, Baogang 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
Recommendations
- Computational experience with a SDP-based algorithm for maximum cut with limited unbalance
- Approximation algorithms for maximum cut with limited unbalance
- Approximating Maximum Cut with Limited Unbalance
- Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
combinatorial optimizationsemidefinite programmingperformance ratiorelaxationrandomized approximation algorithmlimited unbalancemax hypergraph cut
Randomized algorithms (68W20) Combinatorial optimization (90C27) Numerical methods based on nonlinear programming (49M37) Semidefinite programming (90C22)
Cites Work
- The hardness of approximation: Gap location
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Approximation algorithms for maximization problems arising in graph partitioning
- Semidefinite relaxation and nonconvex quadratic optimization
- Some optimal inapproximability results
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Improved approximation algorithms for maximum graph partitioning problems
- On judicious bisections of graphs
- Problems and results on judicious partitions
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A note on balanced bipartitions
- Title not available (Why is that?)
- Balanced judicious bipartitions of graphs
- Approximability of maximum splitting of k-sets and some other Apx-complete problems
- Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
- Judicious partitions of bounded‐degree graphs
- Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- A .699-approximation algorithm for Max-Bisection.
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- An improved rounding method and semidefinite programming relaxation for graph partition
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- Title not available (Why is that?)
- The RPR2 rounding technique for semidefinite programs
- New semidefinite programming relaxations for box constrained quadratic program
- Title not available (Why is that?)
- Approximation algorithms for indefinite complex quadratic maximization problems
- Improved approximations for max set splitting and max NAE SAT
- Title not available (Why is that?)
- Title not available (Why is that?)
- A note on approximating Max-Bisection on regular graphs
- Improved approximation of Max-Cut on graphs of bounded degree
- Approximation algorithms for maximum cut with limited unbalance
- Inapproximability results for set splitting and satisfiability problems with no mixed clauses
- Title not available (Why is that?)
- Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability
- Non-oblivious local search for graph and hypergraph coloring problems
Cited In (7)
- Approximation algorithms for MAX RES CUT with limited unbalanced constraints
- Computational experience with a SDP-based algorithm for maximum cut with limited unbalance
- On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
- A bound on judicious bipartitions of directed graphs
- On the optimality of the random hyperplane rounding technique for MAX CUT
- Unbalanced graph cuts with minimum capacity
- A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
Uses Software
This page was built for publication: An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018887)
