Algoritmi per problemi su matroidi e polimatroidi

I matroidi vennero introdotti per dare una descrizione generale all’idea di indipendenza. Tramite i matroidi è possibile descrivere oggetti della combinatoria, dell’algebra lineare, della teoria dei grafi. Nel presente lavoro introduciamo il concetto e mostriamo alcuni utilizzi: nel capitolo 1 affrontiamo il problema di trovare la base di costo massimo e presentiamo l'algoritmo greedy; nel capitolo 2 discutiamo il problema di trovare l'indipendente di cardinalità massima comune a più matroidi. Nell'ultima parte presentiamo una descrizione poliedrale dei matroidi, trattando una loro generalizzazione, i polimatroidi. Vedremo infine degli algoritmi per risolvere in modo efficiente programmi lineari, la regione dei quali sia un polimatroide.»