Numerical study of semidefinite bounds for the k-cluster problem

DOI10.1016/J.ENDM.2010.05.051MaRDI QIDQ2883586zbMATH OpenOpenAlexFDO

Authors Jérôme Malick, Frédéric Roupin

Publication date 13 May 2012

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2010.05.051

zbMATH Keywords

combinatorial optimizationsemidefinite programming\(k\)-clusterLagrangian duality and relaxation

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Sensitivity, stability, parametric optimization (90C31) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Solving \(k\)-cluster problems to optimality with semidefinite programming
• Computational results of a semidefinite branch-and-bound algorithm for k-cluster
• On semidefinite programming relaxations of maximum \(k\)-section
• Bounds for the quadratic assignment problem using the bundle method
• scientific article; zbMATH DE number 1894380

Cites work

• A Dual Approach to Semidefinite Least-Squares Problems
• A Spectral Bundle Method for Semidefinite Programming
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• CSDP, A C library for semidefinite programming
• Improved approximation algorithms for maximum graph partitioning problems
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• Partial Lagrangian relaxation for general quadratic programming
• Solving \(k\)-cluster problems to optimality with semidefinite programming

Cited in

(8)

• Solving \(k\)-cluster problems to optimality with semidefinite programming
• Recent Advances in Constraints
• Generating cutting planes for the semidefinite relaxation of quadratic programs
• Computational results of a semidefinite branch-and-bound algorithm for k-cluster
• On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
• Box-bisection for solving second-degree systems and the problem of clustering
• Solving clustered low-rank semidefinite programs arising from polynomial optimization
• New perspectives on \(k\)-support and cluster norms

Describes a project that uses

Uses Software

• CSDP

This page was built for publication: Numerical study of semidefinite bounds for the \(k\)-cluster problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2883586)