This paper presents some preliminary results of an ongoing investigation about how different algorithmic building blocks contribute to solving the Maximum Clique problem. In detail, we consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of Dynamic Local Search and the previously proposed Reactive Local Search. The experimental results consider both the empirical hardness, measured by the iterations needed to reach empirical maxima, and the CPU time per iteration.
Reactive and dynamic local search for Max-Clique, does the complexity pay off? / Battiti, Roberto; Mascia, Franco. - ELETTRONICO. - (2006), pp. 1-15.
Reactive and dynamic local search for Max-Clique, does the complexity pay off?
Battiti, Roberto;Mascia, Franco
2006-01-01
Abstract
This paper presents some preliminary results of an ongoing investigation about how different algorithmic building blocks contribute to solving the Maximum Clique problem. In detail, we consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of Dynamic Local Search and the previously proposed Reactive Local Search. The experimental results consider both the empirical hardness, measured by the iterations needed to reach empirical maxima, and the CPU time per iteration.File | Dimensione | Formato | |
---|---|---|---|
techrep.pdf
accesso aperto
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
161.19 kB
Formato
Adobe PDF
|
161.19 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione