Improved approximation algorithms for MAXk-CUT and MAX BISECTION
AlgorithmicaPublished 1 May 1997
Alan Frieze, M. Jerrum
Citations412
SJR quartileQ1
SJR score0.97
SNIP1.11
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Polynomial-time approximation algorithms with nontrivial performance guarantees are presented for the problems of (a) partitioning the vertices of a weighted graph intok blocks so as to maximize the weight of crossing edges, and (b) partitioning the vertices of a weighted graph into two blocks of equal cardinality, again so as to maximize the weight of crossing edges. The approach, pioneered by Goemans and Williamson, is via a semidefinite programming relaxation.
Keywords
Computer ScienceEngineering
The theory of functions
2,269 Citations1932E. C. Titchmarsh
TechnometricsThe Asymptotic Theory of Extreme Order Statistics
1,830 Citations1990John E. Angus, János Galambos
Journal of Computer and System SciencesOptimization, approximation, and complexity classes
1,662 Citations1991Christos H. Papadimitriou, Mihalis Yannakakis
SIAM Journal on OptimizationInterior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
891 Citations1995Farid Alizadeh
It is argued that many known interior point methods for linear programs can be transformed in a mechanical way to algorithms for SDP with proofs of convergence and polynomial time complexity carrying over in a similar fashion.
Proof verification and hardness of approximation problems
741 Citations1992Sanjeev Arora, Carsten Lund +3 more
Proceedings of the 55th Annual ACM Symposium on Theory of Computing
587 Citations2023
Complexity: Knots, Colourings and Counting
312 Citations1993Dominic Welsh
Mathematical programming studiesHeuristic analysis, linear programming and branch and bound
227 Citations1980Laurence A. Wolsey
This work considers two questions arising in the analysis of heuristic algorithms: is there a general procedure involved when analysing a particular problem heuristic and how can heuristic procedures be incorporated into optimising algorithms such as branch and bound.
Polynomial time approximation schemes for dense instances of <i>NP</i>-hard problems
200 Citations1995Sanjeev Arora, David R. Karger +1 more
A unified framework for designing polynomial time approximation schemes (PTASs) for “dense” instances of many NP-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum k-way cut with and without specified terminals, and maximum 3-satisfiability is presented.
Cambridge University Press eBooksComplexity: Knots, Colourings and Countings
184 Citations1993Dominic Welsh
Approximate graph coloring by semidefinite programming
101 Citations2002David R. Karger, R. Motwani +1 more
A randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with min {O(/spl Delta//sup 1/3/log/sup 4/3//spl Delta/), O(n/Sup 1/4/ log n)} colors is given, marking the first non-trivial approximation result as a function of the maximum degree /spl Delta/.
Random Structures and AlgorithmsMAX-CUT has a randomized approximation scheme in dense graphs
79 Citations1996W. Fernandez de la Véga