ROBERTO BATTITI, ALAN A. BERTOSSI, ROMEO RIZZI,
Randomized Greedy Algorithms
for the Hypergraph Partitioning Problem,
Proceedings of the DIMACS Workshop on
Randomization methods in
algorithm design (Princeton, NJ, 1997),
edited by: Panos Pardalos, Sanguthevar Rajasekaran,
and Jose Rolim,
American Mathematical Society, 21-35, 1998.
DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 43,
Amer. Math. Soc., Providence, RI, 1999.
descrizione:
Quando si mette un circuito su piastra
si vorrebbero piazzare metá dei componenti su
una faccia e metá sull'altra,
al tempo stesso minimizzando peró il numero
di collegamenti che debbano poi attraversare la piastra
tramite foro o ponte.
Piú in generale, un problema tipico in VLSI
é quello di piazzare metá oggetti da una parte
e metá dall'altra (=partizionare),
cercando di rompere il minor numero possibile di legami.
Quando ogni legame riguarda coppie di nodi singoli
questo problema é stato catalogato come
GRAPH PARTITIONING ed é stato uno dei primi
ad essere dimostrato NP-completo.
Ma recentemente alcuni problemi nelle applicazioni
sembravano abbisognare di una piú fedele rappresentazione
come problemi di HYPERGRAPH PARTITIONING,
dove sono degli assiemi di oggetti di cardinalitá
possibilmente maggiore di due
a non voler essere separati.
Ovviamente questo complica ulteriormente il problema.
In questo lavoro abbiamo proposto delle semplici euristche
di tipo greedy ed abbiamo osservato
come esse fossero competitive nei confronti di
ben piú sofisticate euristiche proposte
da altri ricercatori.
