Solving k-cluster problems to optimality with semidefinite programming
From MaRDI portal
Publication:1925793
DOI10.1007/S10107-012-0604-1zbMATH Open1257.90068OpenAlexW2046706749MaRDI QIDQ1925793FDOQ1925793
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
Recommendations
- Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
- Numerical study of semidefinite bounds for the \(k\)-cluster problem
- A branch-and-bound algorithm for solving max-\(k\)-cut problem
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- On semidefinite programming relaxations of maximum \(k\)-section
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Semidefinite programming (90C22)
Cites Work
- CSDP, A C library for semidefinite programming
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Title not available (Why is that?)
- On the solution of large-scale SDP problems by the modified barrier method using iterative solvers
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Computing the nearest correlation matrix--a problem from finance
- Numerical Optimization
- A Spectral Bundle Method for Semidefinite Programming
- Regularization Methods for Semidefinite Programming
- A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix
- Some numerical experiments with variable-storage quasi-Newton algorithms
- A preconditioned Newton algorithm for the nearest correlation matrix
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- On the Shannon capacity of a graph
- Clustering and domination in perfect graphs
- Branching rules revisited
- Approximation algorithms for maximization problems arising in graph partitioning
- Semidefinite optimization
- An Interior-Point Method for Semidefinite Programming
- Greedily Finding a Dense Subgraph
- The dense \(k\)-subgraph problem
- Improved approximation algorithms for maximum graph partitioning problems
- A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
- A Dual Approach to Semidefinite Least-Squares Problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Discrete location problems with push-pull objectives
- The discrete p-dispersion problem
- Upper bounds and exact algorithms for \(p\)-dispersion problems
- From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
- Partial Lagrangian relaxation for general quadratic programming
- Numerical study of semidefinite bounds for the \(k\)-cluster problem
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- 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 improved rounding method and semidefinite programming relaxation for graph partition
- The spherical constraint in Boolean quadratic programs
- Title not available (Why is that?)
- Efficient Optimization of Monotonic Functions on Trees
- A Construction Concerning (l p ) � ⊂l q
- Algorithms – ESA 2005
Cited In (14)
- On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study
- An exact semidefinite programming approach for the max-mean dispersion problem
- 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
- Numerical study of semidefinite bounds for the \(k\)-cluster problem
- Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
- On solving the densestk-subgraph problem on large graphs
- k-Clustering Minimum Biclique Completion via a Hybrid CP and SDP Approach
- 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 bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
- Minimum energy configurations on a toric lattice as a quadratic assignment problem
- Order-constrained solutions in \(K\)-means clustering: even better than being globally optimal
Uses Software
This page was built for publication: Solving \(k\)-cluster problems to optimality with semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1925793)
