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. - 11:4(2023), pp. 957-972. [10.1007/s40305-022-00395-8]
Maximum Independent Sets and Supervised Learning
Roberto Montemanni
;Xiaochen Chou
2023
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
6653937e-9811-479d-ba32-66ff1be3866d.pdf
Accesso riservato
Tipologia:
VOR - Versione pubblicata dall'editore
Dimensione
453.8 kB
Formato
Adobe PDF
|
453.8 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
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
