Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
From MaRDI portal
Publication:2287849
DOI10.1007/s13675-019-00110-yzbMath1437.90141OpenAlexW2920857515WikidataQ62706560 ScholiaQ62706560MaRDI QIDQ2287849
Vilmar Jefté Rodrigues de Sousa, Sébastien Le Digabel, Miguel F. Anjos
Publication date: 22 January 2020
Published in: EURO Journal on Computational Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s13675-019-00110-y
semidefinite programminggraph partitioningmaximum \(k\)-cuteigenvalue constraintsemi-infinite formulation
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Cutting Plane Generation through Sparse Principal Component Analysis, Computational study of a branching algorithm for the maximum \(k\)-cut problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Large-scale optimization with the primal-dual column generation method
- An extended edge-representative formulation for the \(K\)-partitioning problem
- Using the primal-dual interior point algorithm within the branch-price-and-cut method
- Gap inequalities for non-convex mixed-integer quadratic programs
- Interior point methods 25 years later
- A multiple search operator heuristic for the max-k-cut problem
- Enhancing RLT relaxations via a new class of semidefinite cuts
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Minimal triangulations of graphs: a survey
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Optimization, approximation, and complexity classes
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Variable neighborhood search
- Stronger linear programming relaxations of max-cut
- Graph partitioning using linear and semidefinite programming
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- A two-level graph partitioning problem arising in mobile wireless communications
- Projection results for the \(k\)-partition problem
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- Facets of the \(k\)-partition polytope
- Gap inequalities for the cut polytope
- Exploiting sparsity for the min \(k\)-partition problem
- The partition problem
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- A semidefinite programming based polyhedral cut and price approach for the maxcut problem
- Computational Approaches to Max-Cut
- Semi-Infinite Programming: Theory, Methods, and Applications
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Approximate graph coloring by semidefinite programming
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Realignment in the National Football League: Did they do it right?
- A Spectral Bundle Method for Semidefinite Programming
- Computational Experience with an Interior Point Cutting Plane Algorithm
- Benchmarking Derivative-Free Optimization Algorithms
- Solving k-Way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Benchmarking optimization software with performance profiles.
