Combinatorial properties and the complexity of a max-cut approximation
From MaRDI portal
Publication:685307
DOI10.1006/eujc.1993.1035zbMath0780.05040OpenAlexW2014079391MaRDI QIDQ685307
Svatopluk Poljak, Charles Delorme
Publication date: 5 December 1993
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/eujc.1993.1035
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items
Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs, On a positive semidefinite relaxation of the cut polytope, On computational capabilities of Ising machines based on nonlinear oscillators, Solving the max-cut problem using eigenvalues, A projection technique for partitioning the nodes of a graph, Some geometric results in semidefinite programming, Semidefinite programming in combinatorial optimization, Computing the Grothendieck constant of some graph classes, Null spaces of correlation matrices, A guide to conic optimisation and its applications, Diffusion bank networks and capital flows, Max-cut and extendability of matchings in distance-regular graphs, A survey of automated conjectures in spectral graph theory, On conjectures involving second largest signless Laplacian eigenvalue of graphs, Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems, The Laplacian spectral radius of a graph under perturbation, Spectral bounds for the maximum cut problem, On Khot’s unique games conjecture, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, New bounds for the maximum cut problem, Semidefinite programming, A randomized approximation scheme for metric MAX-CUT, Laplacian eigenvalues and the maximum cut problem
