Publications

BibTex format

@article{Campos:2023:10.1007/s11081-022-09763-y,
author = {Campos, JS and Misener, R and Parpas, P},
doi = {10.1007/s11081-022-09763-y},
journal = {Optimization and Engineering},
pages = {1983--2004},
title = {Partial lasserre relaxation for sparse max-cut},
url = {http://dx.doi.org/10.1007/s11081-022-09763-y},
volume = {24},
year = {2023}
}

Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - A common approach to solve or find bounds of polynomial optimization problems like Max-Cut is to use the first level of the Lasserre hierarchy. Higher levels of the Lasserre hierarchy provide tighter bounds, but solving these relaxations is usually computationally intractable. We propose to strengthen the first level relaxation for sparse Max-Cut problems using constraints from the second order Lasserre hierarchy. We explore a variety of approaches for adding a subset of the positive semidefinite constraints of the second order sparse relaxation obtained by using the maximum cliques of the graph’s chordal extension. We apply this idea to sparse graphs of different sizes and densities, and provide evidence of its strengths and limitations when compared to the state-of-the-art Max-Cut solver BiqCrunch and the alternative sparse relaxation CS-TSSOS.
AU  - Campos,JS
AU  - Misener,R
AU  - Parpas,P
DO  - 10.1007/s11081-022-09763-y
EP  - 2004
PY  - 2023///
SN  - 1389-4420
SP  - 1983
TI  - Partial lasserre relaxation for sparse max-cut
T2  - Optimization and Engineering
UR  - http://dx.doi.org/10.1007/s11081-022-09763-y
UR  - https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000842585800001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - https://link.springer.com/article/10.1007/s11081-022-09763-y
UR  - http://hdl.handle.net/10044/1/99549
VL  - 24
ER  -

Download

ProfessorRuthMisener

Contact

Location

Summary

Citation

BibTex format

RIS format (EndNote, RefMan)