An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
type: Item
instance of: scholarly article
title: An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
zbMATH Open document ID: 1335.49053
author: Xingxing Yu
author: Xiaoyan Zhang
author: Zan-Bo Zhang
author: Baogang Xu
published in: Science China. Mathematics
publication date: 2015-03-26T00:00:00Z
Mathematics Subject Classification ID: 49M37
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6419670
zbMATH Keywords: max hypergraph cut
zbMATH Keywords: limited unbalance
zbMATH Keywords: randomized approximation algorithm
zbMATH Keywords: performance ratio
zbMATH Keywords: semidefinite programming
zbMATH Keywords: relaxation
zbMATH Keywords: combinatorial optimization
describes a project that uses: Outward rotations
MaRDI profile type: Publication
full work available at URL: s11425-014-4900-5
OpenAlex ID: W2001501791
cites work: Q4263699
cites work: Q2753920
cites work: Non-oblivious local search for graph and hypergraph coloring problems
cites work: Q4251055
cites work: Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
cites work: Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
cites work: Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
cites work: Problems and results on judicious partitions
cites work: Judicious partitions of bounded‐degree graphs
cites work: A note on approximating Max-Bisection on regular graphs
cites work: Improved approximation of Max-Cut on graphs of bounded degree
cites work: Approximation algorithms for maximization problems arising in graph partitioning
cites work: The RPR2 rounding technique for semidefinite programs
cites work: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
cites work: Approximation algorithms for maximum cut with limited unbalance
cites work: Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Inapproximability results for set splitting and satisfiability problems with no mixed clauses
cites work: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
cites work: An improved rounding method and semidefinite programming relaxation for graph partition
cites work: Q2721982
cites work: Some optimal inapproximability results
cites work: Approximation algorithms for indefinite complex quadratic maximization problems
cites work: Improved approximation algorithms for maximum graph partitioning problems
cites work: Approximability of maximum splitting of k-sets and some other Apx-complete problems
cites work: Q4083461
cites work: Semidefinite relaxation and nonconvex quadratic optimization
cites work: The hardness of approximation: Gap location
cites work: Q5743406
cites work: New semidefinite programming relaxations for box constrained quadratic program
cites work: Balanced judicious bipartitions of graphs
cites work: A note on balanced bipartitions
cites work: On judicious bisections of graphs
cites work: A .699-approximation algorithm for Max-Bisection.
cites work: Improved approximations for max set splitting and max NAE SAT
cites work: Q4250183
cites work: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
DOI: 10.1007/S11425-014-4900-5
description: scientific article; zbMATH DE number 6419670