Solving \(k\)-cluster problems to optimality with semidefinite programming
From MaRDI portal
Publication:1925793
DOI10.1007/s10107-012-0604-1zbMath1257.90068OpenAlexW2046706749MaRDI QIDQ1925793
Frédéric Roupin, Jérôme Malick
Publication date: 19 December 2012
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-012-0604-1
Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Numerical Study of Semidefinite Bounds for the k-cluster Problem, Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster, A hybrid three-phase approach for the Max-Mean dispersion problem, On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study, On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods, An exact semidefinite programming approach for the max-mean dispersion problem, Minimum energy configurations on a toric lattice as a quadratic assignment problem, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Improved semidefinite bounding procedure for solving max-cut problems to optimality, Semidefinite relaxations for partitioning, assignment and ordering problems, Semidefinite relaxations for partitioning, assignment and ordering problems, On solving the densestk-subgraph problem on large graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Computing the nearest correlation matrix--a problem from finance
- On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
- Discrete location problems with push-pull objectives
- Improved approximation algorithms for maximum graph partitioning problems
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- On the solution of large-scale SDP problems by the modified barrier method using iterative solvers
- Some numerical experiments with variable-storage quasi-Newton algorithms
- The discrete p-dispersion problem
- The spherical constraint in Boolean quadratic programs
- 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
- Clustering and domination in perfect graphs
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
- An improved rounding method and semidefinite programming relaxation for graph partition
- Branching rules revisited
- Upper bounds and exact algorithms for \(p\)-dispersion problems
- Partial Lagrangian relaxation for general quadratic programming
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Numerical Study of Semidefinite Bounds for the k-cluster Problem
- Efficient Optimization of Monotonic Functions on Trees
- Semidefinite optimization
- A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix
- On the Shannon capacity of a graph
- Numerical Optimization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- CSDP, A C library for semidefinite programming
- A Spectral Bundle Method for Semidefinite Programming
- A Dual Approach to Semidefinite Least-Squares Problems
- [https://portal.mardi4nfdi.de/wiki/Publication:4653077 A Construction Concerning (l p ) � ⊂l q]
- An Interior-Point Method for Semidefinite Programming
- Greedily Finding a Dense Subgraph
- A preconditioned Newton algorithm for the nearest correlation matrix
- Regularization Methods for Semidefinite Programming
- Algorithms – ESA 2005
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- The dense \(k\)-subgraph problem
