Nuovi risultati per il problema - Layouni, Zoubir
29,99 €
inkl. MwSt.
Versandkostenfrei*
Versandfertig in 6-10 Tagen
payback
15 °P sammeln
  • Broschiertes Buch

In questo libro esaminiamo una proprietà speciale di una matrice binaria, nota come "proprietà degli 1 consecutivi". Un blocco consecutivo è una sequenza di 1 consecutivi. Il problema consiste nel trovare una permutazione delle colonne in modo che il numero di blocchi consecutivi nella matrice indotta sia minimo. Si sottolinea che è NP-completo per istanze generali, quindi si presentano le applicazioni che lo riguardano, le varianti e uno stato dell'arte. Il nostro primo contributo consiste nel dimostrare che la CBM è NP-completa anche quando la matrice binaria ha solo due 1 per riga,…mehr

Andere Kunden interessierten sich auch für
Produktbeschreibung
In questo libro esaminiamo una proprietà speciale di una matrice binaria, nota come "proprietà degli 1 consecutivi". Un blocco consecutivo è una sequenza di 1 consecutivi. Il problema consiste nel trovare una permutazione delle colonne in modo che il numero di blocchi consecutivi nella matrice indotta sia minimo. Si sottolinea che è NP-completo per istanze generali, quindi si presentano le applicazioni che lo riguardano, le varianti e uno stato dell'arte. Il nostro primo contributo consiste nel dimostrare che la CBM è NP-completa anche quando la matrice binaria ha solo due 1 per riga, trasformando polinomialmente il problema della catena hamiltoniana di massimo peso in CBM ristretta alle istanze in questione.Un secondo contributo è consistito nel risolvere la domanda: la CBM è approssimabile con garanzia? La risposta è stata trovata sotto forma di un'euristica polinomiale che costruisce permutazioni che hanno come risultato un numero di blocchi consecutivi che non si discosta più del 50% dall'ottimo.
Autorenporträt
O Dr. Zoubir Layouni obteve um doutoramento em ciências informáticas em 2010 pela Université Badji Mokhtar em Annaba, Argélia. Atualmente, é Professor Universitário e Vice-Diretor da Faculdade. Os seus interesses de investigação incluem a otimização, os algoritmos de aproximação e os problemas NP-difíceis.