Improved approximation algorithms for MAX k-CUT and MAX BISECTION

zbMATH Open1135.90420MaRDI QIDQ3499508FDOQ3499508

Publication date: 2 June 2008

Recommendations

Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
scientific article; zbMATH DE number 1762086
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
A .699-approximation algorithm for Max-Bisection.

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (58)

Near-optimal approximation algorithm for simultaneous Max-Cut
Engineering branch-and-cut algorithms for the equicut problem
The Maximum k-Colorable Subgraph Problem and Related Problems
Energy efficient monitoring in sensor networks
Approximation algorithms for the bi-criteria weighted MAX-CUT problem
A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section
Constant factor Lasserre integrality gaps for graph partitioning problems
Mixed linear and semidefinite programming for combinatorial and quadratic optimization
FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Constrained submodular maximization via a nonsymmetric technique
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
Title not available (Why is that?)
Approximation algorithms for MAX RES CUT with limited unbalanced constraints
An improved kernel for max-bisection above tight lower bound
Improved approximation algorithms for maximum graph partitioning problems
Approximation algorithm for MAX DICUT with given sizes of parts
Sharp spectral bounds of several graph parameters using eigenvector norms
Robust discriminative clustering with sparse regularizers
Semi-definite positive programming relaxations for graph \(K_n\)-coloring in frequency assignment.
SDP-based bounds for graph partition via extended ADMM
Spectral partitioning with multiple eigenvectors
Title not available (Why is that?)
Approximation Algorithms for Some Graph Partitioning Problems
Approximating Maximum Cut with Limited Unbalance
Approximate Max \(k\)-Cut with subgraph guarantee
On approximation of max \(\frac{n}{2}\)-uncut problem
Title not available (Why is that?)
Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations
Realignment in the National Football League: Did they do it right?
Complex semidefinite programming and Max-\(k\)-Cut
Title not available (Why is that?)
Three candidate plurality is stablest for small correlations
Title not available (Why is that?)
A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
10 problems for partitions of triangle-free graphs
Complexity of approximating CSP with balance/hard constraints
Laplacian eigenvalues and fixed size multisection
A multiple penalty function method for solving max-bisection problems
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
A .699-approximation algorithm for Max-Bisection.
Clustering with qualitative information
Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
Cone-LP's and semidefinite programs: geometry and a simplex-type method
A new Lagrangian net algorithm for solving max-bisection problems
Title not available (Why is that?)
Approximation algorithms for maximum cut with limited unbalance
Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem
Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds
Energy Efficient Monitoring in Sensor Networks
Maximally stable Gaussian partitions with discrete applications
Approximating max-cut under graph-MSO constraints
Title not available (Why is that?)
A representation theory perspective on simultaneous alignment and classification
Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
Graph-Theoretic Concepts in Computer Science
A combinatorial design approach to MAXCUT

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 Q3499508)