An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
From MaRDI portal
(Redirected from Publication:2018887)
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
Cites work
- scientific article; zbMATH DE number 1617262 (Why is no real title available?)
- scientific article; zbMATH DE number 1670644 (Why is no real title available?)
- scientific article; zbMATH DE number 3503283 (Why is no real title available?)
- scientific article; zbMATH DE number 1303558 (Why is no real title available?)
- scientific article; zbMATH DE number 1304324 (Why is no real title available?)
- scientific article; zbMATH DE number 1342117 (Why is no real title available?)
- A .699-approximation algorithm for Max-Bisection.
- A note on approximating Max-Bisection on regular graphs
- A note on balanced bipartitions
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- An improved rounding method and semidefinite programming relaxation for graph partition
- Approximability of maximum splitting of k-sets and some other Apx-complete problems
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Approximation algorithms for indefinite complex quadratic maximization problems
- Approximation algorithms for maximization problems arising in graph partitioning
- Approximation algorithms for maximum cut with limited unbalance
- Balanced judicious bipartitions of graphs
- Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
- Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
- Improved approximation algorithms for MAX k-cut and MAX BISECTION
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved approximation algorithms for maximum graph partitioning problems
- Improved approximation of Max-Cut on graphs of bounded degree
- Improved approximations for max set splitting and max NAE SAT
- Inapproximability results for set splitting and satisfiability problems with no mixed clauses
- Judicious partitions of bounded‐degree graphs
- New semidefinite programming relaxations for box constrained quadratic program
- Non-oblivious local search for graph and hypergraph coloring problems
- On judicious bisections of graphs
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Problems and results on judicious partitions
- Semidefinite relaxation and nonconvex quadratic optimization
- Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability
- Some optimal inapproximability results
- The RPR2 rounding technique for semidefinite programs
- The hardness of approximation: Gap location
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
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)
