Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION

From MaRDI portal

Publication:679447

Jump to:navigation, search

DOI10.1007/BF02523688zbMath0873.68078OpenAlexW1601503375WikidataQ57401556 ScholiaQ57401556MaRDI QIDQ679447

Alan M. Frieze, Mark R. Jerrum

Publication date: 9 October 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02523688

zbMATH Keywords

semidefinite programming graph connectivity randomized algorithms

Mathematics Subject Classification ID

Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

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, Matrix Relaxations in Combinatorial Optimization, Approximation and hardness results for the max \(k\)-uncut problem, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, A new greedy strategy for maximizing monotone submodular function under a cardinality constraint, Maximizing a non-decreasing non-submodular function subject to various types of constraints, Approximation algorithms for two variants of correlation clustering problem, Judicious partitions of directed graphs, Memetic search for the max-bisection problem, Semidefinite programming in combinatorial optimization, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding, Computational study of valid inequalities for the maximum \(k\)-cut problem, SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY, Universal qudit Hamiltonians, On approximating complex quadratic optimization problems via semidefinite programming relaxations, Exploiting sparsity for the min \(k\)-partition problem, On the approximability of digraph ordering, On semidefinite programming relaxations of maximum \(k\)-section, New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover, A class of spectral bounds for max \(k\)-cut, Computational study of a branching algorithm for the maximum \(k\)-cut problem, An approximation algorithm for maxk-uncut with capacity constraints, Angular synchronization by eigenvectors and semidefinite programming, On bisections of graphs without complete bipartite graphs, A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis, Graph partitioning: an updated survey, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, Approximation and Hardness Results for the Max k-Uncut Problem, Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs, An approximation algorithm for scheduling two parallel machines with capacity constraints., An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis, A semidefinite relaxation based global algorithm for two-level graph partition problem, New algorithms for a simple measure of network partitioning, Unnamed Item, A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem, Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems, Bisections of graphs, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, Cardinality constrained minimum cut problems: complexity and algorithms., The capacitated max \(k\)-cut problem, A semidefinite programming approach to the hypergraph minimum bisection problem, Approximation algorithms for maximum cut with limited unbalance, Approximating the fixed linear crossing number, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, A branch-and-bound algorithm for solving max-\(k\)-cut problem, A modified VNS metaheuristic for max-bisection problems, Algorithmic aspects of homophyly of networks, An improved kernel for max-bisection above tight lower bound, A two-level graph partitioning problem arising in mobile wireless communications, Dominance inequalities for scheduling around an unrestrictive common due date, Iterated linear optimization, Projection results for the \(k\)-partition problem, Approximating the 2-catalog segmentation problem using semidefinite programming relaxations, A branch‐and‐price approach to k‐clustering minimum biclique completion problem, Semidefinite programming and combinatorial optimization, Semi-definite relaxation algorithm of multiple knapsack problem, On the tractability of coloring semirandom graphs, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, Max-bisections of \(H\)-free graphs, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, New algorithms for a simple measure of network partitioning, An approximation algorithm for the partial vertex cover problem in hypergraphs, Correlation clustering in data streams, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, Semidefinite relaxations for partitioning, assignment and ordering problems, Relaxations of Combinatorial Problems Via Association Schemes, Semidefinite Programming and Constraint Programming, Computational Approaches to Max-Cut, 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, Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph, Semidefinite relaxations for partitioning, assignment and ordering problems, A combinatorial algorithm for MAX CSP, A randomised approximation algorithm for the hitting set problem, A Single-Phase, Proximal Path-Following Framework, Approximability Distance in the Space of H-Colourability Problems, New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Approximate Kernel Clustering, A max-cut approach to heterogeneity in cryo-electron microscopy, Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks, On approximation of max-vertex-cover, Unnamed Item, Approximating Max Cut with Limited Unbalance, Semidefinite programming, A note on approximating Max-Bisection on regular graphs, Approximating the maximum quadratic assignment problem, Speeding up a memetic algorithm for the max-bisection problem, Improved approximation algorithms for maximum graph partitioning problems, An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems, Randomized approximation for the set multicover problem in hypergraphs

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:679447&oldid=29963520"