Numerical Study of Semidefinite Bounds for the k-cluster Problem

DOI10.1016/j.endm.2010.05.051zbMath1237.65059OpenAlexW1969992797MaRDI QIDQ2883586

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

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

semidefinite programmingcombinatorial optimization\(k\)-clusterLagrangian duality and relaxation

Mathematics Subject Classification ID

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

Related Items

Generating cutting planes for the semidefinite relaxation of quadratic programs, On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods, Solving \(k\)-cluster problems to optimality with semidefinite programming

Uses Software

• CSDP

Cites Work

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