### Abstract

A γ-quasi-clique in a simple undirected graph refers to a subset of vertices that induces a subgraph with edge density at least γ. When γ equals one, this definition corresponds to a classical clique. When γ is less than one, it relaxes the requirement of all possible edges by the clique definition. Quasi-clique detection has been used in graph-based data mining to find dense clusters, especially in large-scale error-prone data sets in which the clique model can be overly restrictive. The maximum γ-quasi-clique problem, seeking a γ-quasi-clique of maximum cardinality in the given graph, can be formulated as an optimization problem with a linear objective function and a single quadratic constraint in binary variables. This article investigates the Lagrangian dual of this formulation and develops an upper-bounding technique using the geometry of ellipsoids to bound the Lagrangian dual. The tightness of the upper bound is compared with those obtained from multiple mixed-integer programming formulations of the problem via experiments on benchmark instances.

Original language | American English |
---|---|

Journal | INFORMS Journal on Coumputing |

State | E-pub ahead of print - 3 Feb 2020 |

## Fingerprint Dive into the research topics of 'An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph'. Together they form a unique fingerprint.

## Cite this

Miao, Z., & Balasundaram, B. (2020). An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph.

*INFORMS Journal on Coumputing*.