Solving the max-cut problem using semidefinite optimization

Max-cut problem is one of many NP-hard graph theory problems which attracted many researchers over the years. Maximum cuts are useful items including theoretical physics and electronics. But they are best known for algorithmic problem of finding a maximum cutting, commonly called MAXCUT, a relativel...

Full description

Saved in:
Bibliographic Details
Main Authors: Orkia, Derkaoui, Ahmed, Lehireche
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Approximation algorithms
Convex functions
HRVW/KSH/M search direction
Interior-point
Linear programming
Linear research
Optimization
Prediction algorithms
predictor-corrector procedure
primal-dual interior-point method
Semidefinite programming
Symmetric matrices
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Max-cut problem is one of many NP-hard graph theory problems which attracted many researchers over the years. Maximum cuts are useful items including theoretical physics and electronics. But they are best known for algorithmic problem of finding a maximum cutting, commonly called MAXCUT, a relatively well-studied problem, particularly in the context of the approximation. Various heuristics, or combination of optimization and heuristic methods have been developed to solve this problem. Among them is the efficient algorithm of Goemans and Williamson. Their algorithm combines Semidefinite programming and a rounding procedure to produce an approximate solution to the max-cut problem. Semidefinite Programming (SDP) is currently the most sophisticated area of Conic Programming that is polynomially solvable. The SDP problem is solved with interior point methods. In parallel, the development of efficient SDP solvers, based on interior point algorithms, also contributed to the success of this method. In this paper we use a new variant of the solver CSDP (C library for semidfinite programming) to resolve this problem. It is based on a Majorize-Minimize line search algorithm for barrier function optimization. A tangent majorant function is built to approximate a scalar criterion containing a barrier function. The comparison of the results obtained with the classic CSDP and our new variant is promising.
ISSN:2327-1884
DOI:10.1109/CIST.2016.7804990