Algoritmi di approssimazione per la massimizzazione di funzioni submodulari

In the present work we explore the problem of maximizing submodular functions. These functions are a class of functions on descrete sets carachterized by a property of diminishing returns, similar to concavity. Some algorithms will be presented, some randomized, that approximate the maximum value up to a certain fixed factor. It will be shown that a factor of ½ with respect to the global maximum is the best that can be guaranteed to achieve in polynomial time; an algorithm achieving this limit will be shown. Furthermore the problem of maximizing submodular functions subject to a cardinality constraint will be shortly explored, and some approximation algorithms for this problem will be presented. First one for the monotone submodular case (that finds a 1-1/e approximation), and then an algorithm for the general case (that finds a 1/e-approximation).

Nel presente lavoro si esplora il problema della massimizzazione di funzioni submodulari. Queste sono una classe di funzioni su insiemi discreti caratterizzate da una proprietà di rendimenti decrescenti, simile alla concavità. Verranno presentati alcuni algoritmi, anche randomizzati, che approssimano il valore massimo a meno di un certo fattore. Si vedrà anche che un fattore ½ rispetto al valore massimo globale è il meglio che si può avere la garanzia di ottenere in tempo polinomiale; si vedrà anche un algoritmo che raggiunge tale limite. Si esplorerà inoltre brevemente il problema di massimizzare le funzioni submodulari con un vincolo di cardinalità, e si presenteranno due algoritmi di approssimazione per tale problema. Prima uno per il caso di funzione submodulare monotona (che trova una 1-1/e approssimazione), ed uno per il caso generale (che trova una 1/e-approssimazione).