Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
From MaRDI portal
Publication:342176
DOI10.1016/j.cor.2015.07.008zbMath1349.90715OpenAlexW1457372680MaRDI QIDQ342176
Frédéric Roupin, Nathan Krislock, Jérôme Malick
Publication date: 17 November 2016
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2015.07.008
semidefinite programmingcombinatorial optimizationtriangle inequalities\(k\)-cluster problem\(k\)-densest subgraph problem
Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Identifying industrial clusters with a novel big-data methodology: are SIC codes (not) fit for purpose in the internet age?, LP-based dual bounds for the maximum quasi-clique problem, An exact algorithm for semi-supervised minimum sum-of-squares clustering, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, New diagonal bundle method for clustering problems in large data sets, A novel optimization approach towards improving separability of clusters, Improved semidefinite bounding procedure for solving max-cut problems to optimality, An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating, Optimization of product category allocation in multiple warehouses to minimize splitting of online supermarket customer orders, On solving the densestk-subgraph problem on large graphs
Uses Software
Cites Work
- On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
- The discrete p-dispersion problem
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Clustering and domination in perfect graphs
- From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
- On weighted vs unweighted versions of combinatorial optimization problems
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- Solving \(k\)-cluster problems to optimality with semidefinite programming
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- Upper bounds and exact algorithms for \(p\)-dispersion problems
- Partial Lagrangian relaxation for general quadratic programming
- Lectures on Modern Convex Optimization
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Detecting high log-densities
- Strong Duality for Semidefinite Programming
- CSDP, A C library for semidefinite programming
- A Limited Memory Algorithm for Bound Constrained Optimization
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Different Formulations for Solving the HeaviestK-Subgraph Problem
