The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem. In particular, it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted, with measurable effects on the quality of the solutions provided on unseen instances. Empirical results are presented to validate the idea.
Maximum Independent Sets and Supervised Learning / Montemanni, Roberto; Smith, Derek H.; Chou, Xiaochen. - In: JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA. - ISSN 2194-668X. - (2022), pp. 1-16. [10.1007/s40305-022-00395-8]
Maximum Independent Sets and Supervised Learning
Roberto Montemanni
;Xiaochen Chou
2022-01-01
Abstract
The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem. In particular, it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted, with measurable effects on the quality of the solutions provided on unseen instances. Empirical results are presented to validate the idea.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
