Improved approximation algorithms for MAX k-cut and MAX BISECTION
From MaRDI portal
Publication:679447
DOI10.1007/BF02523688zbMATH Open0873.68078DBLPjournals/algorithmica/FriezeJ97OpenAlexW1601503375WikidataQ57401556 ScholiaQ57401556MaRDI QIDQ679447FDOQ679447
Publication date: 9 October 1997
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02523688
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Approximation algorithms (68W25)
Cites Work
- Optimization, approximation, and complexity classes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- MAX-CUT has a randomized approximation scheme in dense graphs
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Heuristic analysis, linear programming and branch and bound
- Notes on Generating Functions of Polynomials: (2) Hermite Polynomials
- THE CORRELATION OF MAXIMA IN SAMPLES DRAWN FROM A BIVARIATE NORMAL DISTRIBUTION1
Cited In (only showing first 100 items - show all)
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- Approximating Max Cut with Limited Unbalance
- The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
- On bisections of graphs without complete bipartite graphs
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Title not available (Why is that?)
- Approximation and hardness results for the max \(k\)-uncut problem
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- Dominance inequalities for scheduling around an unrestrictive common due date
- An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
- A two-level graph partitioning problem arising in mobile wireless communications
- SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY
- A branch‐and‐price approach to k‐clustering minimum biclique completion problem
- On the approximability of digraph ordering
- 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
- A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
- A Single-Phase, Proximal Path-Following Framework
- New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover
- Approximating the fixed linear crossing number
- Max-bisections of \(H\)-free graphs
- Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- Universal qudit Hamiltonians
- Approximation and Hardness Results for the Max k-Uncut Problem
- Exploiting sparsity for the min \(k\)-partition problem
- New formulations for the conflict resolution problem in the scheduling of television commercials
- New algorithms for a simple measure of network partitioning
- A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
- Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
- Approximability Distance in the Space of H-Colourability Problems
- Title not available (Why is that?)
- A semidefinite relaxation based global algorithm for two-level graph partition problem
- New algorithms for a simple measure of network partitioning
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
- A note on approximating Max-Bisection on regular graphs
- Randomized approximation for the set multicover problem in hypergraphs
- Iterated linear optimization
- Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks
- Approximate Kernel Clustering
- Title not available (Why is that?)
- Semi-definite relaxation algorithm of multiple knapsack problem
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite programming
- An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
- An approximation algorithm for scheduling two parallel machines with capacity constraints.
- Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs
- On the tractability of coloring semirandom graphs
- A randomised approximation algorithm for the hitting set problem
- Bisections of graphs
- An improved kernel for max-bisection above tight lower bound
- An approximation algorithm for the partial vertex cover problem in hypergraphs
- Improved approximation algorithms for maximum graph partitioning problems
- Maximizing a non-decreasing non-submodular function subject to various types of constraints
- A max-cut approach to heterogeneity in cryo-electron microscopy
- Title not available (Why is that?)
- On approximation of max-vertex-cover
- Graph partitioning: an updated survey
- Relaxations of Combinatorial Problems Via Association Schemes
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
- An approximation algorithm for maxk-uncut with capacity constraints
- Speeding up a memetic algorithm for the max-bisection problem
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- A semidefinite programming approach to the hypergraph minimum bisection problem
- Title not available (Why is that?)
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- Semidefinite programming in combinatorial optimization
- A class of spectral bounds for max \(k\)-cut
- Approximating the maximum quadratic assignment problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- A branch-and-bound algorithm for solving max-\(k\)-cut problem
- Correlation clustering in data streams
- Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
- Projection results for the \(k\)-partition problem
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
- Semidefinite programming and combinatorial optimization
- A .699-approximation algorithm for Max-Bisection.
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Memetic search for the max-bisection problem
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Computational Approaches to Max-Cut
- A combinatorial algorithm for MAX CSP
- Matrix Relaxations in Combinatorial Optimization
- Title not available (Why is that?)
- Approximation algorithms for maximum cut with limited unbalance
- On semidefinite programming relaxations of maximum \(k\)-section
- Cardinality constrained minimum cut problems: complexity and algorithms.
- An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- Angular synchronization by eigenvectors and semidefinite programming
- A modified VNS metaheuristic for max-bisection problems
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)
