Improved approximation algorithms for MAX k-cut and MAX BISECTION
From MaRDI portal
(Redirected from Publication:679447)
Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
Recommendations
Cites work
- scientific article; zbMATH DE number 437298 (Why is no real title available?)
- scientific article; zbMATH DE number 3137533 (Why is no real title available?)
- scientific article; zbMATH DE number 3592801 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 1263204 (Why is no real title available?)
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- Heuristic analysis, linear programming and branch and bound
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- MAX-CUT has a randomized approximation scheme in dense graphs
- Notes on Generating Functions of Polynomials: (2) Hermite Polynomials
- Optimization, approximation, and complexity classes
- THE CORRELATION OF MAXIMA IN SAMPLES DRAWN FROM A BIVARIATE NORMAL DISTRIBUTION1
Cited in
(only showing first 100 items - show all)- An efficient semidefinite programming relaxation for the graph partition problem
- A single-phase, proximal path-following framework
- Algorithmic aspects of homophyly of networks
- A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
- scientific article; zbMATH DE number 7758351 (Why is no real title available?)
- Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
- Approximability Distance in the Space of H-Colourability Problems
- Approximation algorithms for two variants of correlation clustering problem
- scientific article; zbMATH DE number 2063458 (Why is no real title available?)
- Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
- Maximizing Several Cuts Simultaneously
- Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
- A semidefinite relaxation based global algorithm for two-level graph partition problem
- New algorithms for a simple measure of network partitioning
- Judicious partitions of directed graphs
- The capacitated max \(k\)-cut problem
- Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
- Graph-Theoretic Concepts in Computer Science
- An approximation algorithm for max \(k\)-uncut with capacity constraints
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- Approximating Max Cut with Limited Unbalance
- Near-optimal approximation algorithm for simultaneous Max-Cut
- Randomized approximation for the set multicover problem in hypergraphs
- A note on approximating Max-Bisection on regular graphs
- On bisections of graphs without complete bipartite graphs
- Approximation algorithms for the bi-criteria weighted MAX-CUT problem
- Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology
- Relaxations of combinatorial problems via association schemes
- Iterated linear optimization
- Semi-definite relaxation algorithm of multiple knapsack problem
- Constant factor Lasserre integrality gaps for graph partitioning problems
- scientific article; zbMATH DE number 1787231 (Why is no real title available?)
- Semidefinite programming
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
- An approximation algorithm for scheduling two parallel machines with capacity constraints.
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs
- A randomised approximation algorithm for the hitting set problem
- Bisections of graphs
- On the tractability of coloring semirandom graphs
- scientific article; zbMATH DE number 5734227 (Why is no real title available?)
- An improved kernel for max-bisection above tight lower bound
- Improved approximation algorithms for maximum graph partitioning problems
- An approximation algorithm for the partial vertex cover problem in hypergraphs
- Maximizing a non-decreasing non-submodular function subject to various types of constraints
- A max-cut approach to heterogeneity in cryo-electron microscopy
- A max-cut approximation using a graph based MBO scheme
- scientific article; zbMATH DE number 5232308 (Why is no real title available?)
- Approximation and hardness results for the max \(k\)-uncut problem
- On approximation of max-vertex-cover
- Approximation and hardness results for the max \(k\)-uncut problem
- An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
- Dominance inequalities for scheduling around an unrestrictive common due date
- Approximating Maximum Cut with Limited Unbalance
- A two-level graph partitioning problem arising in mobile wireless communications
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- Graph partitioning: an updated survey
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
- On approximation of max \(\frac{n}{2}\)-uncut problem
- New bounds for the -k-cut and chromatic number of a graph
- Speeding up a memetic algorithm for the max-bisection problem
- A semidefinite programming approach to the hypergraph minimum bisection problem
- scientific article; zbMATH DE number 1688377 (Why is no real title available?)
- Matrix relaxations in combinatorial optimization
- Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- A branch‐and‐price approach to k‐clustering minimum biclique completion problem
- Computational approaches to MAX-cut
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Semidefinite programming in combinatorial optimization
- A class of spectral bounds for max \(k\)-cut
- Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
- An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation
- Approximating the maximum quadratic assignment problem
- A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
- The Lovász theta function for random regular graphs and community detection in the hard regime
- Approximating the fixed linear crossing number
- Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations
- scientific article; zbMATH DE number 1762086 (Why is no real title available?)
- Max-bisections of \(H\)-free graphs
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- A branch-and-bound algorithm for solving max-\(k\)-cut problem
- Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
- Correlation clustering in data streams
- Projection results for the \(k\)-partition problem
- Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Semidefinite programming and combinatorial optimization
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs
- Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
- Universal qudit Hamiltonians
This page was built for publication: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679447)
