A note on the Lasserre hierarchy for different formulations of the maximum independent set problem

Miguel F Anjos, Y. Emine, Z. Sune

Research output: Contribution to journalArticlepeer-review

Abstract

In this note, we consider several polynomial optimization formulations of the maximum independent set problem and the use of the Lasserre hierarchy with these different formulations. We demonstrate using computational experiments that the choice of formulation may have a significant impact on the resulting bounds. We also provide theoretical justifications for the observed behavior.
Original languageEnglish
Number of pages14
JournalOperations Research Letters
Volume49
Issue number1
Early online date3 Nov 2020
DOIs
Publication statusPublished - 31 Jan 2021

Fingerprint

Dive into the research topics of 'A note on the Lasserre hierarchy for different formulations of the maximum independent set problem'. Together they form a unique fingerprint.

Cite this