Triangles improve 0.878 approximation for Maxcut
From MaRDI portal
Cites work
- A combinatorial, primal-dual approach to semidefinite programs
- A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- An experimental evaluation of semidefinite programming and spectral algorithms for max cut
- Approximating max-cut on bounded degree graphs: tighter analysis of the FKL algorithm
- Approximating the Cut-Norm via Grothendieck's Inequality
- Better balance by being biased: a 0.8776-approximation for {\textsc{Max Bisection}}
- Collective dynamics of `small-world' networks
- Combinatorial properties and the complexity of a max-cut approximation
- Complexity of maximum cut on interval graphs
- Correlation clustering, maximizing agreements via semidefinite programming
- Decompositions of triangle-dense graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Emergence of Scaling in Random Networks
- Expander flows, geometric embeddings and graph partitioning
- Fast SDP algorithms for constraint satisfaction problems
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Finding Hamiltonian circuits in interval graphs
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Gadgets, Approximation, and Linear Programming
- Generalized vertex covering in interval graphs
- High-dimensional statistics. A non-asymptotic viewpoint
- How to Round Any CSP
- scientific article; zbMATH DE number 5485545 (Why is no real title available?)
- scientific article; zbMATH DE number 5764850 (Why is no real title available?)
- scientific article; zbMATH DE number 3510345 (Why is no real title available?)
- scientific article; zbMATH DE number 3633251 (Why is no real title available?)
- scientific article; zbMATH DE number 1224949 (Why is no real title available?)
- scientific article; zbMATH DE number 1496855 (Why is no real title available?)
- scientific article; zbMATH DE number 1559516 (Why is no real title available?)
- scientific article; zbMATH DE number 3307332 (Why is no real title available?)
- Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved approximation of Max-Cut on graphs of bounded degree
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- Lower bounds for max-cut in H-free graphs via semidefinite programming
- Max cut and the smallest eigenvalue
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Maximizing quadratic programs: extending Grothendieck's inequality
- Maximum cut on line and total graphs
- On the \(k\)-coloring of intervals
- On the max-cut of sparse random graphs
- On the optimality of the random hyperplane rounding technique for MAX CUT
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- P-Complete Approximation Problems
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Reducibility among combinatorial problems
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Scheduling Split Intervals
- Semidefinite programs on sparse random graphs and their application to community detection
- Semidefinite relaxation and nonconvex quadratic optimization
- Spectral triadic decompositions of real-world networks
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The MAX-CUT of sparse random graphs
- The maximum cardinality cut problem in co-bipartite chain graphs
- The maximum k-colorable subgraph problem for chordal graphs
- The NP-completeness column: an ongoing guide
- The RPR2 rounding technique for semidefinite programs
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Unit disk graph recognition is NP-hard
This page was built for publication: Triangles improve 0.878 approximation for Maxcut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346856)
