Mi sono imbattuto nel seguente problema algoritmico durante la sperimentazione con algoritmi di classificazione. Gli elementi sono classificati in una polisierarchia, ciò che capisco essere un poset con una singola radice. Devo risolvere il seguente problema, che assomiglia molto allo set cover problem.Selezione di k-sotto-posets
Ho caricato la descrizione del problema Latex-ed here.
La creazione di un algoritmo di approssimazione che soddisfi 1 & 2 è abbastanza semplice, basta iniziare dai vertici di G e "salire" o iniziare dalla radice e "scendere". Supponiamo di iniziare alla radice, espandere iterativamente i vertici e quindi rimuovere i vertici non necessari fino ad avere almeno k sub-reticoli. Il limite di approssimazione dipende dal numero di figli di un vertice, che è OK per la mia applicazione.
Qualcuno sa se questo problema ha un nome proprio, o forse la versione ad albero del problema? Sarei interessato a scoprire se questo problema è NP-difficile, forse qualcuno ha idee per un buon problema NP-difficile da ridurre o ha un algoritmo polinomiale per risolvere il problema. Se entrambi raccolgono your million dollar price. ;)
Non capisco. Se scegli S '= {r} dove r è la radice, allora \ sigma (r) = V. Vuoi dire sigma (s) per essere tutti gli elementi minori o uguali a re maggiore o uguale a s (dove sempre meno l'ordine parziale del reticolo)? – deinst
@deinst Ecco perché 'k' è lì: per rendere il problema più interessante :)' S = {r} 'è la soluzione per' k = 1'. – Bolo
@dareios Si potrebbe voler correggere due errori minori nella dichiarazione del problema. 1) Il secondo paragrafo non è vero in generale, dipende dalla scelta di 'G' (a meno che manchi qualcosa, se' G' contiene due figli e nient'altro, allora 'S = G' è una soluzione con' l = k = 2'. 2) Nel terzo ultimo paragrafo, probabilmente intendi: "[...] vogliamo ancora mantenere ** 2 **." – Bolo