Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914490047528960 |
|---|---|
| author | Ciccarelli, Fabio Dose, Valerio Furini, Fabio Monaci, Marta |
| author_facet | Ciccarelli, Fabio Dose, Valerio Furini, Fabio Monaci, Marta |
| contents | We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that none of them can give a performance guarantee. We further analyze the relative strength among the three upper bounds by determining, for every choice of a ratio between any two of them, the largest values it can attain and providing families of instances for which such values can be reached. Our results show that, for each pair of upper bounds, there exist appropriately chosen instances on which either bound is tighter than the other. Our theoretical analysis is complemented by extensive computational experiments on two benchmark datasets: the standard DIMACS instances and randomly generated instances, providing practical insights into the empirical strength of the upper bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_06898 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem Ciccarelli, Fabio Dose, Valerio Furini, Fabio Monaci, Marta Optimization and Control Combinatorics We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that none of them can give a performance guarantee. We further analyze the relative strength among the three upper bounds by determining, for every choice of a ratio between any two of them, the largest values it can attain and providing families of instances for which such values can be reached. Our results show that, for each pair of upper bounds, there exist appropriately chosen instances on which either bound is tighter than the other. Our theoretical analysis is complemented by extensive computational experiments on two benchmark datasets: the standard DIMACS instances and randomly generated instances, providing practical insights into the empirical strength of the upper bounds. |
| title | Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem |
| topic | Optimization and Control Combinatorics |
| url | https://arxiv.org/abs/2507.06898 |