A Complementary Pivoting Approach to the Maximum Weight Clique Problem

DOI10.1137/S1052623400381413zbMath1035.90072OpenAlexW2067535145MaRDI QIDQ2784445

Marcello Pelillo, Alessio Massaro, Immanuel M. Bomze

Publication date: 23 April 2002

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s1052623400381413

zbMATH Keywords

heuristicsquadratic programminglinear complementaritycombinatorial optimizationmaximum weight cliquepivoting methods

Mathematics Subject Classification ID

Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Extreme-point and pivoting methods (90C49)

Related Items

Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata ⋮ A review on algorithms for maximum clique problems ⋮ Fast Cluster Detection in Networks by First Order Optimization ⋮ Graph polynomials from principal pivoting ⋮ A variable neighborhood search heuristic for the maximum ratio clique problem ⋮ On a continuous approach for the maximum weighted clique problem ⋮ A new trust region technique for the maximum weight clique problem ⋮ A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs ⋮ A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs ⋮ The combinatorics of pivoting for the maximum weight clique. ⋮ A hybrid heuristic for the maximum clique problem ⋮ Simple ingredients leading to very efficient heuristics for the maximum clique problem ⋮ On the Convergence of Mirror Descent beyond Stochastic Convex Programming ⋮ On independent cliques and linear complementarity problems ⋮ Quartic formulation of standard quadratic optimization problems

This page was built for publication: A Complementary Pivoting Approach to the Maximum Weight Clique Problem