A semidefinite programming based polyhedral cut and price approach for the maxcut problem
From MaRDI portal
Publication:2506169
DOI10.1007/s10589-005-5958-3zbMath1103.90074OpenAlexW2130312263MaRDI QIDQ2506169
Kartik Krishnan, John E. Mitchell
Publication date: 28 September 2006
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10589-005-5958-3
Related Items
A second-order cone cutting surface method: Complexity and application ⋮ Memetic search for the max-bisection problem ⋮ A matrix generation approach for eigenvalue optimization ⋮ Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel ⋮ Comments on: Stability in linear optimization and related topics. A personal tour ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ Optimization over structured subsets of positive semidefinite matrices via column generation ⋮ Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems ⋮ Preprocessing composite cutting procedure: an approach to the integer model ⋮ Polyhedral approximations of the semidefinite cone and their application ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints ⋮ Speeding up a memetic algorithm for the max-bisection problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Positive definite completions of partial Hermitian matrices
- Geometric algorithms and combinatorial optimization
- Path optimization for graph partitioning problems
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Stronger linear programming relaxations of max-cut
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- The integration of an interior-point cutting plane method within a branch-and-price algorithm
- The expected relative error of the polyhedral approximation of the max- cut problem
- On a positive semidefinite relaxation of the cut polytope
- Exact ground states of two-dimensional \(\pm J\) Ising spin glasses
- Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
- Global Optimization with Polynomials and the Problem of Moments
- On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- The Cutting-Plane Method for Solving Convex Programs
- A unifying framework for several cutting plane methods for semidefinite programming
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- An Efficient Heuristic Procedure for Partitioning Graphs
- How Good is the Goemans--Williamson MAX CUT Algorithm?
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Semidefinite relaxation and nonconvex quadratic optimization
- User'S guide To Lipsol linear-programming interior point solvers V0.4
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- SDPLIB 1.2, a library of semidefinite programming test problems
- A Spectral Bundle Method for Semidefinite Programming
- Computational Experience with an Interior Point Cutting Plane Algorithm
- On the cut polytope
- Reducibility among Combinatorial Problems
- Some optimal inapproximability results
- Geometry of cuts and metrics
